#define _USE_MATH_DEFINES #include using namespace std; // repetition #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define rep(i, n) for (int i = 0; i < (int)(n); i++) // container util #define all(x) (x).begin(), (x).end() // debug #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) \ cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \ << " " << __FILE__ << endl; // typedef typedef long long lint; typedef unsigned long long ull; typedef complex Complex; typedef pair Pi; typedef tuple TP; typedef vector vec; typedef vector mat; // constant const int MOD = (int)1e9 + 7; const int INF = (int)1e18; const int dx[] = {0, 1, 0, -1}; const int dy[] = {1, 0, -1, 0}; const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1}; const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1}; // conversion inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; } template inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); } // template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } // vector dijkstra(vector>& G, int s) { vector dist(G.size(), INF); priority_queue, greater> que; dist[s] = 0; que.emplace(dist[s], s); // cost, to while (!que.empty()) { Pi p = que.top(); que.pop(); long long cost = p.first; int cur = p.second; if (dist[cur] < cost) continue; for (auto nv : G[cur]) { int next_cost = dist[cur] + nv.second; if (dist[nv.first] <= next_cost) continue; dist[nv.first] = next_cost; que.emplace(dist[nv.first], nv.first); } } return dist; } int main() { ios::sync_with_stdio(false); cin.tie(0); int N, M, P, Q, T; cin >> N >> M >> P >> Q >> T; P--; Q--; vector> G(N, vector()); int a, b, c; for (int i = 0; i < M; i++) { cin >> a >> b >> c; a--; b--; G[a].push_back(make_pair(b, c)); G[b].push_back(make_pair(a, c)); } vector dist = dijkstra(G, 0); vector Pdist = dijkstra(G, P); vector Qdist = dijkstra(G, Q); if (dist[P] + Pdist[Q] + Qdist[0] <= T) { cout << T << endl; return 0; } if (max(2 * dist[P], 2 * dist[Q]) > T) { cout << -1 << endl; return 0; } lint tmin = INF; for (int i = 0; i < N; i++) { if (i == 0 || i == P || i == Q) continue; for (int j = 0; j < N; j++) { if (j == 0 || j == P || j == Q) continue; lint div = max(dist[P] - dist[i] + Pdist[j], dist[Q] - dist[i] + Qdist[j]); lint d = Pdist[0] - Pdist[j]; if (dist[i] + div + d > T) continue; tmin = min(tmin, div); } } cout << T - tmin << endl; return 0; }