题目描述
飞船发动机有 n 个能量节点，节点之间有 m 条线路相连。自检程序会从节点 1 发出强度是 b 的检测信号，检测信号在经过每条线路的时候都会有减弱一定的值。节点 i 的信号阈值是 f[i]。在经过每个节点的时候，检测信号的强度不会变化。检测程序需要计算出，在最终信号强度大于 0 的情况下，到达节点 n 经过的所有节点中，最大信号阈值最低可以是多少。
输入
第一行 3 个整数，n,m,b（n,b <= 10000,m <= 20000）,保证图联通。
第二行 n 个整数，分别表示 f[1]到 f[n](f[i] <= 100000)。
接下来 m 行，每行 3 个整数 u,v,w，表示连接节点 u 和节点v 的线路长度是 w(1 <= u,v, <= n,w <= 100000)。
输出
一个整数，表示在最终信号强度大于 0 的情况下，到达节点 n经过的所有节点中，最大信号阈值最低可以是多少。
样例输入
4 4 8
8 5 6 10
2 1 2
2 4 1
1 3 4
3 4 3样例输出
10