import heapq def dijkstra(n, graph, start): INF = float('inf') dist = [INF] * (n + 1) dist[start] = 0 heap = [] heapq.heappush(heap, (0, start)) while heap: current_dist, u = heapq.heappop(heap) if current_dist > dist[u]: continue for v, c in graph[u]: if dist[v] > dist[u] + c: dist[v] = dist[u] + c heapq.heappush(heap, (dist[v], v)) return dist n, m, P, Q, T = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a, b, c = map(int, input().split()) graph[a].append((b, c)) graph[b].append((a, c)) # Compute shortest paths from 1, P, Q d1 = dijkstra(n, graph, 1) dp = dijkstra(n, graph, P) dq = dijkstra(n, graph, Q) max_time = -1 # Check Scenario A: 1->P->Q->1 and 1->Q->P->1 time1 = d1[P] + dp[Q] + dq[1] if time1 <= T: max_time = max(max_time, T) time2 = d1[Q] + dq[P] + dp[1] if time2 <= T: max_time = max(max_time, T) # Check Scenario B: Split at some city X for X in range(1, n+1): max_pq = max(2 * dp[X], 2 * dq[X]) total_time = 2 * d1[X] + max_pq if total_time <= T: candidate = T - max_pq if candidate > max_time: max_time = candidate # Check Scenario D: Separate visits to P and Q time_p = 2 * d1[P] time_q = 2 * d1[Q] max_pq_separate = max(time_p, time_q) if max_pq_separate <= T: candidate = T - max_pq_separate max_time = max(max_time, candidate) print(max_time if max_time != -1 else -1)