3370 - 人猿泰山
在原始大森林里长大的泰山，早就学会了森林里的猿猴们攀爬树木和通过藤条在森林的树木之间游走的本事。
森林有 N 棵树（树的编号为 1 \sim N），第 i 棵树的高度是 H_i 米。在森林里，泰山可以在一棵树上爬上、爬下，他每向上爬 1 米或者向下爬 1 米都需要 1 秒的时间。
如果两棵树之间有藤条，他还可以借助藤条在两棵不同的树之间荡来荡去，从编号为 X_j 和编号为 Y_j 的树之间借助藤条荡来或者荡去都需要 T_j 秒的时间。经统计，森林中有 M 对树之间设有藤条。
因为体重的影响，泰山在树之间每荡 1 秒，他会顺着藤条下降 1 米。如果泰山在一棵树上的高度为 h 的位置，借助藤条荡到对面的树，荡过去的时间为 t，理论上泰山荡到对面的树上之后，他在树上的高度是 h-t。如果 h-t 大于对面树的高度或者小于 0，都不能顺利荡到对面的树上。如果荡不过去，泰山可以先选择在当前树上爬上或者爬下，让自己处于合适的高度后再尝试荡过去。
请编程计算出，泰山从编号为 1 的树上高度为 S 米的位置出发，只能借助藤条在树之间游走，想要荡到编号为 N 的树的顶端（即：高度为 H_N 的位置），最少需要多少秒？
第 1 行输入三个整数 N,M,S，含义如题所述。
接下来 N 行，第 i 行的整数 H_i，表示第 i 棵树的高度为 H_i 米。
接下来 M 行，第 j 行有三个整数 X_j,Y_j,T_j 代表在编号为 X_j 的树和编号为 Y_j 的树之间荡来或者荡去需要 T_j 秒的时间。
输出泰山荡到编号为 N 的数的顶端，最少需要的时间。如果泰山无法成功的到达目标位置，请输出 -1。
输入
5 5 0 50 100 25 30 10 1 2 10 2 5 50 2 4 20 4 3 1 5 4 20
输出
110
输入
2 1 0 1 1 1 2 100
输出
-1
输入
4 3 30 50 10 20 50 1 2 10 2 3 10 3 4 10
输出
100
样例 1 解释
以下方案可以以最短的时间，到达目标位置。
沿着树 1 向上爬 50 米 。
从树 1 荡到树 2 。
从树 2 荡到树木 4 。
从树 4 荡到树 5 。
沿着树 5 向上爬 10 米。
数据范围
对于 50\% 的数据，满足 2 \le N \le 1000，1 \le M \le 3000。
对于 100\% 的数据，满足 2 \le N \le 10^5，1 \le M \le 3 \times 10^5，1 \le H_i \le 10^9，1 \le T_j \le 10^9，1 \le X_j \neq Y_j \le N，0 \le S \le H_1。
