zzx是一个究极大懒逼，他懒到这题的题面都不想写了，于是直接向你提出了问题。
zzx现在处于他的宿舍XX-XXX，他现在必须要赶去上课，而x校由于疫情影响的原因，大多数道路都被禁止通过，现在x校内只有n个路口允许通过，这n个路口的编号为1、2、3、...、n
路口之间存在m条双向道路，连接着两个路口，从路口a走到路口b将会消耗zzx一定的体力值，
同时，当且仅当zzx经过一个路口时，森源哥才会向他收取一定的保护费，
现在假设zzx所处的宿舍就是1号路口，n号路口为zzx要到的教室，而zzx的体力值为x，刚刚出发时，zzx的精力充沛，体力是满的，倘若zzx的体力值降低到负数，那么zzx将无法继续行动。
zzx在前往教室的途中希望保护好自己的生活费，因此他想知道，他在经过的所有路口中，森源哥会向他收取的最多的一次保护费最小值是多少？
第一行，包括三个整数，n、m、x，分别有n个路口、m条道路以及zzx的体力为x
接下来n行，
每行包括一个整数vi，代表zzx在经过第i个路口时森源哥会收取的保护费
在接下来m行，
每行包含三个整数，a，b，c，代表路口a与路口b之间存在一条双向道路，需要花费zzx一共c点体力
(2 <= n <= 1e4, 1 <= m <= 5e4, 1 <= a,b <= n, 1 <= x, c, v <= 1e9)
仅输出一个整数，代表zzx花费最多的一次保护费的最小值，
若他无法到达教室，请输出“GG!”，不包含双引号
4 4 8 2 1 0 7 4 2 1 1 3 1 4 1 1 1 2 1
7