힙을 이용한 다익스트라

• 현재 가장 가까운 노드를 저장하기 위해 우선순위 큐를 이용
• 시간 복잡도 : O(E*logV), E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산 : O(E*logE)
• E <= V^2 이므로 O(E*logE) = O(E*logV^2) = O(E*logV)

# 우선순위 큐 임포트
import heapq

# 초기화 과정
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())  # 시작 노드
adj_list = [[] for _ in range(n + 1)]
min_dist_table = [INF] * (n + 1)  # 최단거리 테이블
for _ in range(m):  # node_list 구성
    i, j, w = map(int, input().split())
    adj_list[i].append((j, w))  # i에서 j로 갈 때 가중치 w

# 방문하지 않은 노드들 중에서, 가장 최단 거리가 짧은 노드는 우선순위 큐를 통해 얻을 것

# 다익스트라 알고리즘
def dijkstra(start):
    # 1. 출발 노드를 설정하고, 최단 거리 테이블을 초기화한다.
    # 가중치를 튜플의 1원소로 넣음으로써 가중치를 우선순위로
    pri_queue = []
    heapq.heappush(pri_queue, (0, start))
    min_dist_table[start] = 0
    while pri_queue:
        # 2. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다.
        dist, now = heapq.heappop(pri_queue)
        # 방문처리 확인
        if min_dist_table[now] < dist:
            continue
        # 3. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
        for adj_node in adj_list[now]:
            cost = dist + adj_node[1]
            # 계산한 거리가 더 짧은 경우 테이블 갱신, 힙에 삽입
            if cost < min_dist_table[adj_node[0]]:
                min_dist_table[adj_node[0]] = cost
                heapq.heappush(pri_queue, (cost, adj_node[0]))

dijkstra(start)

# 출력
for i in range(1, n + 1):
    if min_dist_table[i] == INF:
        print("inf")
    else:
        print(min_dist_table[i])

'''
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
'''