// #pragma GCC optimize ("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC target ("avx,avx2,fma") #include using std::cin, std::cout, std::cerr; using ll = long long; int main() { std::ios::sync_with_stdio(false); int n, m, p, q, t; cin >> n >> m >> p >> q >> t; std::vector>> e(n + 1); for(int i = 1; i <= m; i ++) { int u, v, w; cin >> u >> v >> w; e[u].push_back({v, w}); e[v].push_back({u, w}); } std::vector d(n + 1), dp(n + 1), dq(n + 1); auto dijkstra = [&](int s, std::vector &d) { std::set> set; d.assign(n + 1, 1e18L); d[s] = 0; for(int i = 1; i <= n; i ++) set.insert({d[i], i}); while(!set.empty()) { int x = set.begin()->second; set.erase(set.begin()); for(auto [i, w] : e[x]) { if(d[x] + w < d[i]) { set.erase({d[i], i}); d[i] = d[x] + w; set.insert({d[i], i}); } } } }; dijkstra(1, d); dijkstra(p, dp); dijkstra(q, dq); ll ans = -1; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= n; j ++) { ll sep = std::max(dp[i] + dp[j], dq[i] + dq[j]); bool ok = d[i] + d[j] + sep <= t; if(ok) { if(ans == -1 || ans < t - sep) ans = t - sep; } } } if(d[p] + d[q] + dp[q] <= t) ans = t; cout << ans << '\n'; }