다익스트라, 우선순위 큐 - 1753번: 최단경로

from collections import defaultdict
import heapq, sys

# 입력이 많은 경우 최적화해주기
input = sys.stdin.readline

V, E = map(int, input().split())

K = int(input())
graph = defaultdict(list)

for i in range(E):
    line = list(map(int, input().split()))
    u, v, w = line[0], line[1], line[2]
    graph[u].append((v, w))


def dijkstra(start):
    dist = [float("inf")] * (V + 1)
    dist[start] = 0
    heap = []

    heapq.heappush(heap, (0, start))

    while heap:
        cost, node = heapq.heappop(heap)

        if dist[node] < cost:
            continue

        for c, w in graph[node]:
            new_cost = cost + w

            if new_cost < dist[c]:
                dist[c] = new_cost
                heapq.heappush(heap, (new_cost, c))

    return dist


dist = dijkstra(K)

for i in range(1, V + 1):
    # 경로 존재하지 않는 경우(초기화값이 그대로인 경우)
    if dist[i] == float("inf"):
        print("INF")
    else:
        print(dist[i])