解题思路

• 将状态扩展为分层图：层编号为已使用好石次数 $c\in[0,k]$，状态为 $(v,c)$。

• 转移分两类（设到达点为 $v$，边基础代价为 $w$）：

  • 不用好石：层内转移 $(u,c)\to(v,c)$，代价 $w+\max(a_v,0)$（坏石必加、好石不加）。
  • 用好石（仅当 $a_v<0$ 且 $c<k$）：跨层 $(u,c)\to(v,c+1)$，代价 $w+a_v$（可能为负）。

• 由于层内边权均为非负（至少 $w\ge 1$），可用 $k+1$ 次 Dijkstra 的分层松弛套路：

  • 先在 $c=0$ 层，设 $d_0[1]=0$ 其余为无穷，跑一次 Dijkstra（仅用层内转移，代价 $w+\max(a_v,0)$）。

题目内容

在一个奇幻王国里，有 $n$ 个城市(编号依次为 $1$ 到 $n$ )和 $m$ 条双向道路，第 $i$ 条道路连接城市 $u_i$ 和 $v_i$ ， 基础通行时间为正整数 $w_i$ 。此外，王国中每个城市都存在 $1$个中枢魔法石，每个魔法石有一个能量值，非负能量值的魔法石称之为「坏魔法石」，负数能量值的魔法石称之为「好魔法石」，坏魔法石会增加通行所需时间，好魔法石会减少通行所需时间(增加和减少的时间即为能量值的多少)，如果好魔法石足够强力，甚至可以实现时间倒流。

坏魔法石将会强制生效，导致基础通行时间增加，无法被控制。

好魔法石可以控制，选择是否生效，但使用好魔法石的总次数存在限制，第 $k$ 次使用好魔法石生效以后，之后将无法利用任何城市的好魔法石来减少通行时间。换句话说，单次行程中好法石总使用次数不超过 $k$ 次。

魔法石不会消失，可以多次使用。

当你从城市 $u$ 前往城市 $v$ 时，路径的实际通行时间计算如下：

通行时间=城市 $u$ 到城市 $v$ 的道路基础通行时间加上城市 $v$ 生效的魔法石能量值。

请计算从城市 $1$ 到城市 $n$ 的最小实际通行时间，注意，您可以重复经过城市和道路。特别地，如果无论如何都无法到达城市 $n$ ，直接输出 $NO$ 。

输入描述

第一行输入三个整数 $n,m,k(2≤n≤10^3;1≤m≤min${$2×10^3,\frac{n×(n-1)}{2}$}$;1≤k≤10^3)$

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(-10^5 ≤ a_i≤ 10^5)$，其中 $a_i$ 表示第 $i$ 个城市的魔法石能量。

接下来 $m$ 行，第 $i$ 行输入三个整数 $u_i, v_i, w_i(1≤ u_i,v_i≤n;u_i≠v_i;1≤w_i≤10^5)$ ，表示城市 $u_i$ 与城市 $v_i$ 之间存在一条同行时间为 $w_i$ 的路径。除此之外，保证任意两个城市之间至多存在一条道路。

注意，本题不保证图的连通性，即可能存在两个城市之间无法通过任何路径互相到达的情况。

输出描述

如果无论如何都无法到达城市 $n$ ，直接输出下 $NO$ ，否则输出一个整数，表示从城市 $1$ 到城市 $n$ 的最少实际通行时间。

样例1

输入

5 5 2
0 0 0 -10 0
1 2 1
2 3 1
3 5 1
1 4 6
4 5 1

输出

-13

说明

在这个样例中，唯一的最优走法是 $1→2→3→5→4→5→4→5$，实际通行时间为 $1+1+1+(1-10)+1+(1-10)+1$ 。