Description
某个国家有n个城市，编号为1，2，3，...n,这个国家修建了m条双向的公路。每条公路连接两个城市。沿着某天公路，开车从一个城市到另一个城市，需要花费一定的汽油。
开车每经过一个城市，都会被收取一定的费用（包括起点和终点城市）。所有收费站都在城市中，在城市间的公路上没有任何的收费站。 现在要开车从城市u到城市v（1<=u,v<=n）,汽车最多可以装下s升的汽油。在出发的时候，车的油箱是满的，并且在路上不能加油。 在能到达目的地的前提下，收费站交费中最多的一次最少是多少。
Input
第一行5个正整数，n,m,u,v,s
接下来n行，每行一个正整数fi，表示城市i收费站的收费
再接下来m行，每行3个正整数，ai，bi，ci（1<=ai,bi<=n）,表示城市ai和bi之间有一条公路，ci表示该公路花费的汽油量。
Output
一个整数，表示交费最多的一次的最小值。
如果无法到达目的地，输出-1.
4 4 2 3 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3
HINT
【问题规模】
对于60%的数据，满足n<=200,m<=10000,s<=200
对于100%的数据，满足n<=10000,m<=50000,s<=1000000000
对于100%的数据，满足ci<=1000000000,fi<=1000000000,
可能有两条边连接着相同的城市。