#include using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; ll N, M, P, Q, T; vector> G[2005]; void dijkstra(vector& dist, ll st){ vector visited(N, false); dist[st] = 0; priority_queue,vector>,greater>> q; q.push(make_pair(0,st)); while(!q.empty()){ pair p = q.top(); q.pop(); if(visited[p.second]) continue; visited[p.second] = true; dist[p.second] = p.first; FOR(it,G[p.second]){ if(!visited[it->first]){ q.push(make_pair(p.first + it->second, it->first)); } } } } int main(){ cin >> N >> M >> P >> Q >> T; rep(i,M){ ll a, b, c; cin >> a >> b >> c; G[a].emplace_back(b, c); G[b].emplace_back(a, c); } vector dist_st(N,-1), dist_P(N,-1), dist_Q(N,-1); dijkstra(dist_st, 1); dijkstra(dist_P, P); dijkstra(dist_Q, Q); ll ret = -1; if(dist_st[P] + dist_P[Q] + dist_st[Q] <= T){ ret = T; } REP(x,1,N+1){ REP(y,1,N+1){ ll sum = dist_st[x]; sum += max(dist_P[x], dist_Q[x]); sum += max(dist_P[y], dist_Q[y]); sum += dist_st[y]; if(sum <= T){ ret = max(ret, T - max(dist_P[x], dist_Q[x]) - max(dist_P[y], dist_Q[y])); } } } cout << ret << endl; return 0; }