#include #include #include #include #include using namespace std; struct Edge{ int to; int64_t cost; Edge(int to, int64_t cost): to(to), cost(cost) {} }; const int64_t inf = 1e18; vector dijkstra(vector> g, int s) { int n = g.size(); vector d(n, inf); d[s] = 0; priority_queue> q; q.emplace(0, s); while (q.size() > 0) { int64_t dist; int v; tie(dist, v) = q.top(); q.pop(); dist *= -1; for (const auto &e: g[v]) { if (dist + e.cost < d[e.to]) { d[e.to] = dist + e.cost; q.emplace(d[e.to] * (-1), e.to); } } } return d; } int main() { int n, m, p, q; int64_t t; cin >> n >> m >> p >> q >> t; p--; q--; vector> g(n); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; g[a].emplace_back(b, c); g[b].emplace_back(a, c); } auto d0 = dijkstra(g, 0), dp = dijkstra(g, p), dq = dijkstra(g, q); int64_t ans = -1; for (int v = 0; v < n; v++) { auto time = t - d0[v] * 2 - max(dp[v], dq[v]) * 2; if (time < 0) continue; ans = max(ans, d0[v] * 2 + time); if ((d0[v] + dp[v] + dq[v]) * 2 <= t) { ans = max(ans, t); } // cout << v << " " << d0[v] * 2 + time << endl; } cout << ans << endl; return 0; }