def oi(): return int(input()) def os(): return input() def mi(): return list(map(int, input().split())) input_count = 0 N, M, START, GOAL = mi() G = {i:[] for i in range(N)} for i in range(M): A,B,C = mi() # Gの第三項に引き継ぎたいものを載せる # 何個目~ならi # 経路復元なら (A,B)など 行先だけ保存しておけばいいかも G[A].append((B, C)) G[B].append((A, C)) # V: 頂点数 # g[v] = {(w, cost)}: # 頂点vから遷移可能な頂点(w)とそのコスト(cost) # r: 始点の頂点 from heapq import heappush, heappop INF = 1<<55 # 経路復元の時はコメントアウト部分を解除 def dijkstra(N, G, s): dist = [INF] * N que = [(0, s)] dist[s] = 0 # # 経路復元用 # edge = {i:set([]) for i in range(N)} # # コスト同じものを持つか # reached = {i:{j:False for j in range(N)} for i in range(N)} while que: c, v = heappop(que) if dist[v] < c: continue for t, cost in G[v]: # if reached[v][t]: # continue if dist[v] + cost < dist[t]: dist[t] = dist[v] + cost # 経路復元用 # edge[t] = set([ind]) heappush(que, (dist[t], t)) # reached[v][t] = True # コストが同じものもどうにかしたいならここ追加 # elif dist[v] + cost == dist[t]: # reached[v][t] = True # edge[t].add(ind) # heappush(que, (dist[t], t)) return dist#edge dist = dijkstra(N, G, START) from collections import deque deq = deque([[GOAL, -1, [GOAL]]]) output = [] ret = None while deq: node, old_node, root = deq.pop() if node == START: strs = "_".join(list(map(str, root[::-1]))) if ret is None: ret = strs else: ret = min(ret, strs) continue for next_node, cost in G[node]: if next_node != old_node: if dist[node] - dist[next_node] == cost: temp = root[:] deq.append((next_node, node, temp+[next_node])) print(*ret.split("_"))