🧭 複数の例

import sys
import heapq

input = sys.stdin.readline
INF = 1e9


def dijkstra(start):
    heap = []
    heapq.heappush(heap, (0, start))  # 가중치 , 간선
    distance[start] = 0
    while heap:
        cost, index = heapq.heappop(heap)
        if distance[index] < cost:
            continue
        # 목적지까지 거리가 현재 인덱스의 cost보다 작을 경우에는
        # 굳이 다음걸 확인할 필요가 없다.
        for next, c in arr[index]:
            if distance[next] > cost + c:
            # 목적지 next인덱스의 가중치보다 현재 인덱스의 가중치 + (현재인덱스에서 목적지 간선의 가중치)가
            # 더 작을경우에 가중치를 업데이트 시켜준다
                distance[next] = cost + c
                # 가중치 업데이트
                heapq.heappush(heap, [cost + c, next])


n, m = map(int, input().split())
start = int(input())
arr = [[] for i in range(n + 1)]
distance = [INF for i in range(n + 1)]
for i in range(m):
    u, v, w = map(int, input().split())
    # u에서 v로 가는 가중치는 w이다.
    arr[u].append([v, w])
dijkstra(start)
for i in range(1, n + 1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])