时间限制：1秒　　内存限制：256M

---

【题目描述】

　　在某个遥远的国家里，有 \(n\) 个城市。编号为 \(1 ,2,3,…,n\)。

　　这个国家的政府修建了 \(m\) 条双向的公路。每条公路连接着两个城市。沿着某条公路，开车从一个城市到另一个城市，需要花费一定的汽油。

　　开车每经过一个城市，都会被收取一定的费用（包括起点和终点城市）。所有的收费站都在城市中，在城市间的公路上没有任何的收费站。

　　小红现在要开车从城市 \(u\) 到城市 \(v(1≤u,v≤n)\)。她的车最多可以装下 \(s\) 升的汽油。在出发的时候，车的油箱是满的，并且她在路上不想加油。

　　在路上，每经过一个城市，她要交一定的费用。如果她某次交的费用比较多，她的心情就会变得很糟。所以她想知道，在她能到达目的地的前提下，她交的费用中最多的一次最少是多少。这个问题对于她来说太难了，于是她找到了聪明的你，你能帮帮她吗？

【输入格式】

　　第一行五个正整数，\(n,m,u,v,s\)。分别表示有 \(n\) 个城市，\(m\) 条公路，从城市 \(u\) 到城市 \(v\)，车的油箱的容量为 \(s\) 升。
　　接下来有 \(n\) 行，每行一个正整数，\(f_i\)，表示经过城市 \(i\)，需要交费 \(f_i\) 元。
　　再接下来有 \(m\) 行，每行三个正整数，\(a_i，b_i，c_i\)。表示城市 \(a_i\) 和城市 \(b_i\) 之间有一条公路，如果从城市 \(a_i\) 到城市 \(b_i\)，或者从城市 \(b_i\) 到城市 \(a_i\)，需要用 \(c_i\) 升汽油。

【输出格式】

　　仅一个整数，表示小红交费最多的一次的最小值，如果她无法到达城市 \(v\)，输出 -1。

【输入输出样例1】

　Input

4 4 2 3 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

　Output

8

【输入输出样例2】

　Input

4 4 2 3 3
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

　Output

-1

【数据限制】

　　对于 \(60\%\) 的数据，\(n≤200\)，\(m≤10000\)，\(s≤200\)，。
　　对于 \(100\%\) 的数据，\(n≤10000\)，\(m≤50000\)，\(s≤1000000000\)。
　　对于 \(100\%\) 的数据，\(c_i≤1000000000\)，\(f_i≤1000000000\)。

【来源】

　　Mr.he