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, f"{A}_{B}")) G[B].append((A, C, f"{B}_{A}")) # 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)} while que: c, v = heappop(que) if dist[v] < c: continue for t, cost, ind in G[v]: if dist[v] + cost < dist[t]: dist[t] = dist[v] + cost # 経路復元用 edge[t] = set([ind]) heappush(que, (dist[t], t)) # コストが同じものもどうにかしたいならここ追加 elif dist[v] + cost == dist[t]: edge[t].add(ind) heappush(que, (dist[t], t)) return edge ret = dijkstra(N, G, START) START = START GOAL = GOAL # もし文字列でハッシュ化してたらここで解除 temp = ret.keys() for k in temp: c = [] for v in ret[k]: c.append(tuple(map(int, list(v.split("_"))))) ret[k] = sorted(c) def keiro_with_dijkstr(START, GOAL): def keiro_hukugen(node, old_node): keiro_list = [] for next_node in ret[node]: nn = (set(next_node)-set([node])).pop() if nn != old_node: flg, keiro = keiro_hukugen(nn, node) if flg: return flg, keiro + [node] if node == START: return True, [START] return False, keiro_list return keiro_hukugen(GOAL, -1) print(*keiro_with_dijkstr(START, GOAL)[1])