1 #include <bits/stdc++.h> 2 #define inf 2147483647 3 using namespace std; 4 int n, m, u, v, s, f[10005], e[10005], head[1000500], d[10005], ans, tot, l, r; 5 void input() { 6 freopen("input.txt", "r", stdin); 7 // freopen("output.txt","w",stdout); 8 } 9 struct A { 10 int v, w, next; 11 } lu[1000500]; 12 void add(int x, int y, int z) { 13 lu[++tot].v = y; 14 lu[tot].w = z; 15 lu[tot].next = head[x]; 16 head[x] = tot; 17 } 18 void read() { 19 int a, b, c; 20 scanf("%d%d%d%d%d", &n, &m, &u, &v, &s); 21 for (int i = 1; i <= n; i++) { 22 scanf("%d", &f[i]); 23 e[i] = f[i]; 24 } 25 sort(e + 1, e + n + 1); 26 for (int i = 1; i <= m; i++) { 27 scanf("%d%d%d", &a, &b, &c); 28 add(a, b, c); 29 add(b, a, c); 30 } 31 } 32 deque<int> q; 33 bool spfa(long long minn) { 34 for (int i = 0; i <= n; i++) d[i] = inf; 35 q.push_back(u); 36 d[u] = 0; 37 while (q.size()) { 38 int now = q.front(); 39 q.pop_front(); 40 if (f[now] > minn) 41 continue; 42 for (int i = head[now]; i; i = lu[i].next) { 43 if (f[lu[i].v] > minn) 44 continue; 45 if (d[lu[i].v] > d[now] + lu[i].w) { 46 d[lu[i].v] = d[now] + lu[i].w; 47 if (q.size() && d[lu[i].v] < d[q.front()]) 48 q.push_front(lu[i].v); 49 else 50 q.push_back(lu[i].v); 51 } 52 } 53 } 54 return d[v] <= s; 55 } 56 void work() { 57 int l = 1, r = n; 58 while (l <= r) { 59 int j = (l + r) >> 1; 60 if (spfa(e[j])) { 61 ans = e[j]; 62 r = j - 1; 63 } else 64 l = j + 1; 65 } 66 if (ans == 0) 67 printf("-1 "); 68 else 69 printf("%d ", ans); 70 } 71 int main() { 72 // input(); 73 read(); 74 work(); 75 return 0; 76 }