#include using namespace std; constexpr int INF = 1'000'000'009; struct Edge{ int to; int cost; Edge(int to, int cost):to(to), cost(cost) {} }; vector dijkstra(int start, const vector> &Es){ int N = Es.size(); vector dist(N, INF); dist[start] = 0; priority_queue, vector>, greater>> pq; pq.push(make_pair(0, start)); while (not pq.empty()){ int d, v; tie(d, v) = pq.top(); pq.pop(); if (d > dist[v]) continue; dist[v] = d; for (auto &uc : Es[v]){ int u = uc.to; int new_d = d + uc.cost; if (new_d < dist[u]){ dist[u] = new_d; pq.push(make_pair(new_d, u)); } } } return dist; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int N, M, P, Q, T; cin >> N >> M >> P >> Q >> T; --P; --Q; vector> Es(N, vector()); for (int m = 0; m < M; ++m){ int a, b, c; cin >> a >> b >> c; Es[a - 1].emplace_back(Edge(b - 1, c)); Es[b - 1].emplace_back(Edge(a - 1, c)); } auto dist0 = dijkstra(0, Es); auto distP = dijkstra(P, Es); auto distQ = dijkstra(Q, Es); if (dist0[P] + distP[Q] + distQ[0] <= T){ cout << T << endl; return 0; } long long record = -1; for (int r = 0; r < N; ++r){ for (int s = r; s < N; ++s){ long long t = max(distP[r] + distP[s], distQ[r] + distQ[s]); if (dist0[r] + dist0[s] + t <= T) record = max(record, T - t); } } cout << record << endl; return 0; }