题目内容

在一张包含 $n$ 个节点和 $m$ 条无向边的图上，节点编号为 $1$ 到 $n$。每条边连接 $u_i$ 和 $v_i$，通过它所需的基础时间为 $w_i$（$w_i > 0$）。 每个节点 $v$ 有一个整数权值 $a_v$。当你从节点 $u$ 沿边移动到节点 $v$ 时，行进耗时按以下规则计算：

• 首先，你必定会额外消耗 $\max(0, a_v)$ 的时间（若 $a_v \le 0$ 则此项为 $0$）。
• 然后，如果 $a_v < 0$，你可以选择激活该节点的一次加速，这将使本次行进耗时再减少 $|a_v|$（即加上 $a_v$）。整个旅程中，你最多可以进行 $k$ 次这样的加速激活。 求从节点 $1$ 出发到达节点 $n$ 的最小总行进耗时。你可以重复经过节点和边。若无论如何都无法到达节点 $n$，输出 exttt{NO}。

约束条件：

• $2 \le n \le 1000$，$1 \le m \le \min(2000, \frac{n(n-1)}{2})$，$1 \le k \le 1000$
• $|a_i| \le 10^5$，$1 \le w_i \le 10^5$