有n个城市，编号为 1,2,3,... ,n。城市之间有 m条双向的公路，每条公路连接着两个城市。从公路一端的城市走到另一端的城市，会损失力气。每次经过一个城市，都会被收取一定的过路费(包括起点和终点)。路上并没有收费站。小明从城市1出发，最终要到达地市n停下，而他的力气最多为 s，出发时他的力气是满的。如果他到达目的地,所剩力气值变成负数了，则他就无法到达城市 n，在旅途中力气是不会恢复的。小明不希望花很多钱，他想知道，在可以到达城市 n 的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。如果他无法到达城市 n，输出 NO。输入格式第一行3个正整数n,m,s，表示有 n(n<=10099)个城市，mm<=50009)条公路，小明满额力气为 s(s<=le9)。第二行 n个正整数，分别表示城市 1到城市 n 需要交的费用。再接下来有m行，每行3个正整数x,y(1=x,y<n),z(<=1000)。表示城市x和城市y之间有一条路，从x到y或者从y到x 都需要花费 z 的力气。可能有边连接着相同的城市。输出格式输出一行，一个整数，表示小明能够到达城市 n 时交费最多的一次的最小值;如果他无法到达城市n，则输出NO程序如下。

组合题

有n个城市，编号为 1,2,3,... ,n。城市之间有 m条双向的公路，每条公路连接着两个城市。从公路一端的城市走到另一端的城市，会损失力气。每次经过一个城市，都会被收取一定的过路费(包括起点和终点)。路上并没有收费站。小明从城市1出发，最终要到达地市n停下，而他的力气最多为 s，出发时他的力气是满的。如果他到达目的地,所剩力气值变成负数了，则他就无法到达城市 n，在旅途中力气是不会恢复的。小明不希望花很多钱，他想知道，在可以到达城市 n 的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。如果他无法到达城市 n，输出 NO。输入格式

第一行3个正整数n,m,s，表示有 n(n<=10099)个城市，mm<=50009)条公路，小明满额力气为 s(s<=le9)。

第二行 n个正整数，分别表示城市 1到城市 n 需要交的费用。再接下来有m行，每行3个正整数x,y(1=x,y<n),z(<=1000)。表示城市x和城市y之间有一条路，从x到y或者从y到x 都需要花费 z 的力气。可能有边连接着相同的城市。输出格式

输出一行，一个整数，表示小明能够到达城市 n 时交费最多的一次的最小值;如果他无法到达城市n，则输出NO

程序如下。