import heapq def dijkstra(n, adj, 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 adj[u]: if dist[v] > dist[u] + c: dist[v] = dist[u] + c heapq.heappush(heap, (dist[v], v)) return dist def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]); idx +=1 M = int(input[idx]); idx +=1 P = int(input[idx]); idx +=1 Q = int(input[idx]); idx +=1 T = int(input[idx]); idx +=1 adj = [[] for _ in range(N+1)] for _ in range(M): a = int(input[idx]); idx +=1 b = int(input[idx]); idx +=1 c = int(input[idx]); idx +=1 adj[a].append((b, c)) adj[b].append((a, c)) d1 = dijkstra(N, adj, 1) d_p = dijkstra(N, adj, P) d_q = dijkstra(N, adj, Q) combined_time = d1[P] + d_p[Q] + d1[Q] if combined_time <= T: print(T) return max_overlap = -1 for X in range(1, N+1): for Y in range(1, N+1): split_time = max(d_p[X] + d_p[Y], d_q[X] + d_q[Y]) total_time = d1[X] + split_time + d1[Y] if total_time <= T: current_overlap = T - split_time if current_overlap > max_overlap: max_overlap = current_overlap print(max_overlap if max_overlap != -1 else -1) if __name__ == '__main__': main()