import sys
input = sys.stdin.readline
from collections import deque
import heapq
INF = sys.maxsize
N = int(input())
M = int(input())
graph = [[] for i in range(N+1)]
money = [INF]*(N+1)
route = [[] for i in range(N+1)]
for i in range(M):
x1,x2,w = map(int,input().split())
graph[x1].append((x2,w))
start,goal = map(int,input().split())
hq = []
heapq.heappush(hq,(0,start,0))
while hq:
w,x,last = heapq.heappop(hq)
if money[x] <= w:
continue
money[x] = w
route[x] = route[last][:]
route[x].append(last)
for i in graph[x]:
x1,w1 = i
heapq.heappush(hq,(w+w1,x1,x))
print(money[goal])
print(len(route[goal]))
print(" ".join(map(str,route[goal][1:])),end=" ")
print(goal)
전형적인 다 익스트라 문제인데 최소비용만을 구하는 것이 아니라 최소비용을 갖기 위한 경로까지 출력해야 하는 문제이다.
다 익스트라의 heapq에 들어가는 tuple에 비용과 현 위치, 그리고 추가로 이전 위치까지 데이터로 넣어준 뒤, 비용 list와 함께 route list를 만들어, 비용이 초기화될 때마다 route를 이전 위치의 route로 초기화시켜주는 방식으로 해결하였다.
다 익스트라의 원리를 이해했다면 쉽게 풀 수 있는 문제이다.
오늘의 교훈) 알고리즘을 무지성으로 쓰지 말고 원리를 이해하자