#!/usr/bin/env python3 from heapq import * inf = 1_000_000_000_000 n, m, c, r = map(int, input().split()) c -= 1 r -= 1 g = [[] for _ in range(n)] for _ in range(m): u, v, w = map(int, input().split()) u -= 1 v -= 1 g[u].append((v, w)) g[v].append((u, w)) # All vs all distances def dijkstra(s): dist = [inf] * n dist[s] = 0 h = [(0, s)] while not len(h) == 0: (d, u) = heappop(h) if d > dist[u]: continue for (v, w) in g[u]: if d + w < dist[v]: dist[v] = d + w heappush(h, (d + w, v)) return dist dist = [dijkstra(u) for u in range(n)] far = [[v for v in range(n) if dist[u][v] == max(dist[u])] for u in range(n)] # This is the max distance till certain catching. # Initializes to 0 for leaves and infinity for others. catch_dist = [0 if len(g[u]) == 1 else inf for u in range(n)] change = True while change: change = False for u in range(n): if catch_dist[u] != inf: continue catch_dist[u] = min(inf, max(dist[u][v] + catch_dist[v] for v in far[u])) if catch_dist[u] < inf: change = True # Potentially handle the first step separately: # In this turn the cop may have a unique path to the robber, and can exclude a few positions for the robber to go to. component = [0] * n component[c] = 1 for i in range(n + 1): for u in range(n): if component[u] == 1: for v, _ in g[u]: if v != r: # Exclude the robber from the component. component[v] = 1 # If the robber has exactly 1 neighbour in the component, exclude all points in the component. if sum(component[v] for v, _ in g[r]) == 1: catch_dist[r] = min( inf, max( (dist[r][v] + catch_dist[v] for v in far[r] if component[v] == 0), ), ) if catch_dist[r] != inf: print(dist[c][r] + catch_dist[r]) # print("yes") else: print('impossible') # print("no")