题目描述

BingYu 生活在一处神秘、广袤而美妙的空间里。

然而，有一天，这处空间不知如何突然被历史课的车轮碾过陷入了剧烈的失衡当中，不论如何，现在 BingYu 该跑路了。

这片空间可以被描述为一个由 $n$ 个节点与 $m$ 条边构成的无向图，其中不存在重边与自环。 BingYu 最初位于 $1$ 号节点上，目标是逃到第 $n$ 号节点处。

链接着各个节点的边有两种：零号路径与一号路径。 BingYu 自某个节点沿着零号路径移动至相连的节点无需消耗时间，而沿着一号路径移动则需要花费 $1$ 个单位的时间。失衡影响下的节点非常不稳定，每个节点都有一个临界值 $t_i$ ,一旦 BingYu 消耗的时间达到 $t_i$ ，第 $i$ 号节点便会立刻崩塌， BingYu 无法前往已经崩塌的节点，也无法在已经崩塌的节点上立足。

现在， BingYu 想要知道，自己到底有没有可能在这片梦中空间被完全摧毁之前逃离？他需要你的帮助。

输入格式

第一行输入两个被空格隔开的正整数 $N \enspace M$ $(2 \le N \le 10^5,1 \le M \le min(\frac{N\cdot (N-1)}{2},10^5))$ 代表节点和边的数量。

第二行输入 $N$ 个被空格隔开的正整数 $t_1,t_2,...,t_n$ $(1 \le t_1,t_2,...,t_n \le 10^5)$ 代表每个节点的失衡临界值。

接下来的 $M$ 行，每行输入三个被空格隔开的正整数 $u \enspace v \enspace x$ $(1 \le u,v \le N , x \in \lbrack 0,1 \rbrack )$ ，代表第 $u$ 号节点和第 $v$ 号节点之间存在一条边，当 $x=0$ 时代表这条边是零号路径，$x=1$ 时则是一号路径 。

输出格式

如果 BingYu 能够成功逃出，先输出 $\textbf{YES}$ ，然后在下一行输出一个正整数，代表 BingYu 逃离需要的最短时间。

否则，输出 $\textbf{NO}$ 。

$\textbf{请注意，本题没有开启 YES/NO 的 special judge，请严格按照 YES/NO 的格式输出。}$

样例

7 9
5 3 8 2 4 3 3
1 2 1
1 3 1
2 4 1
3 4 0
4 5 1
3 6 1
7 5 0
7 6 1
5 6 1

YES
2

4 4
3 2 2 1
1 2 1
1 3 1
2 4 1
3 4 1

NO

样例解释

对于样例一， 空间的结构如图所示。

最优路线为 $1 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 7$ 。

对于样例二，在 BingYu 自 $1$ 号节点进行任意一次移动后， $4$ 号节点便会崩塌，导致 BingYu 无论如何都无法成功逃脱。