다익스트라 탬플릿 코드

from heapq import heappush, heappop


v, e = map(int, input().split())
st = int(input())
graph = [[] for _ in range(v + 1)]
distance = [99999999] * (v + 1)
distance[0] = 0
for i in range(e):
    x, y, val = map(int, input().split())
    graph[x].append([val, y])


def dijkstra(graph, num, distance):
    q = []
    heappush(q, [0, num])
    distance[num] = 0

    while q:
        w, number = heappop(q)

        if w > distance[number]:
            continue

        for weight, route in graph[number]:
            cost = w + weight
            if cost < distance[route]:
                
                distance[route] = cost
                heappush(q, [cost, route])


dijkstra(graph, st, distance)
for dis in distance[1:]:
    if dis == 99999999:
        print('INF')
    else:
        print(dis)