#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int MAX_N = 2010; ll D[MAX_N][MAX_N]; vector E[MAX_N]; struct Node { int v; ll dist; Node(int v = -1, ll dist = -1) { this->v = v; this->dist = dist; } bool operator>(const Node &n) const { return dist > n.dist; } }; void set_dist(int v) { priority_queue , greater> pque; pque.push(Node(v, 0)); bool visited[MAX_N + 1]; memset(visited, false, sizeof(visited)); while (not pque.empty()) { Node node = pque.top(); pque.pop(); if (visited[node.v]) continue; visited[node.v] = true; D[v][node.v] = node.dist; D[node.v][v] = node.dist; for (int u : E[node.v]) { pque.push(Node(u, node.dist + D[node.v][u])); } } } int main() { int N, M, P, Q, T; cin >> N >> M >> P >> Q >> T; memset(D, 0, sizeof(D)); ll a, b, c; for (int i = 0; i < N; ++i) { cin >> a >> b >> c; E[a].push_back(b); E[b].push_back(a); D[a][b] = c; D[b][a] = c; } set_dist(1); set_dist(P); set_dist(Q); ll d1 = D[1][P]; ll d2 = D[P][Q]; ll d3 = D[Q][1]; ll bd = max(d1, d3); ll td = d1 + d2 + d3; fprintf(stderr, "d1: %lld, d2: %lld, d3: %lld, td: %lld\n", d1, d2, d3, td); if (td <= T) { cout << T << endl; } else if (2 * bd > T) { cout << -1 << endl; } else { ll max_d = 0; for (int i = 2; i <= N; ++i) { ll fd = D[1][i]; for (int j = 2; j <= N; ++j) { ll d = max(D[i][P] + D[P][j], D[i][Q] + D[Q][j]); ll rd = D[j][1]; if (fd + d + rd > T) continue; ll t = T - d; max_d = max(max_d, t); } } cout << max_d << endl; } return 0; }