def oi(): return int(input()) def os(): return input() def mi(): return list(map(int, input().split())) # import sys # input = sys.stdin.readline 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) for k in G.keys(): G[k] = sorted(G[k]) import heapq deq = [[str(START).rjust(4,"0"), START, -1]] heapq.heapify(deq) ret = None # count = 0 while deq: root, node, old_node = heapq.heappop(deq) if node == GOAL: ret = root break for next_node, cost in G[node]: if next_node != old_node: if dist[next_node] - dist[node] == cost: hoge = str(next_node).rjust(4,"0") heapq.heappush(deq, (root+f" {hoge}", next_node, node)) # count += 1 # if count == 3: # print(deq) print(*map(int, ret.split(" ")))