BOJ - 11779 - 최소비용 구하기 2

import sys
from heapq import heappush, heappop

def Dijkstra(start, end, graph, V):
    heap = []
    distance = [1e9] * (V +1)
    distance[start] = 0
    heappush(heap, (0, start))

    ret = [0 for _ in range(V+1)]
    while heap:
        weight, location = heappop(heap)

        if distance[location] < weight:
            continue

        for l, w in graph[location]:
            w += weight
            if w < distance[l]:

                distance[l] = w
                heappush(heap, (w, l))
                ret[l]=location

    arr = []
    idx = end
    cnt = 0
    while ret[idx] != 0:
        arr.append(idx)
        idx = ret[idx]

    arr.append(idx)
    arr.reverse()
    print(distance[end])
    print(len(arr))
    print(*arr)

def solution():
    N = int(input())
    M = int(input())
    graph = [[] for _ in range(N + 1)]

    for _ in range(M):
        u, v, w = map(int, sys.stdin.readline().split())
        graph[u].append([v, w])

    start, end = map(int, sys.stdin.readline().split())

    Dijkstra(start, end, graph, N)

solution()

https://www.acmicpc.net/problem/11779