import sys
import heapq

INF = sys.maxsize


def solution(self, graph, start_node):
    # 1. 출발점으로부터 모든 노드까지의 최단거리를 표현하는 1차원 딕셔너리 distances -> {node: distance}
    #   - 각 노드들에 대한 초기거리는 무한대를 의미하는 INF 로 넣기
    distances = {node: INF for node in graph}  # ex. {'A': INF, 'B': INF, 'C': INF, ...}

    # 2. 초기화
    #   - distances 를 start_node 로 초기화 >> 자기 자신을 방문하는 의미이므로, Set 0
    #   - 방문 노드 표현을 위한 우선순위 큐 heap 을 start_node 로 초기화
    #   - 우선순위 큐에 삽입시 정렬을 위한 인덱스를 node list 의 거리를 나타내는 0번 값으로 하기 때문에([0, 'A'] 처럼)
    #   - MinHeapq 방식에 따라 가까운 거리 순으로 자동 정렬 (우선순위 큐로서의 완전 이진 트리 살펴보기)
    distances[start_node] = 0  # ex. {'A': 0, 'B': INF, 'C': INF, ...}
    visit_queue = []
    heapq.heappush(visit_queue, [distances[start_node], start_node])  # ex. [[0, 'A']]

    # 3. 모든 노드를 방문하며 start_node 로부터의 최단거리 탐색
    #   - heap 에 더 이상 원소가 남지 않게 되면 모든 노드를 방문한 것
    while visit_queue:
        # 정렬된 우선순위 큐를 이용해 가장 인접한 노드 방문!(욕심쟁이)
        visited_distance, visited_node = heapq.heappop(visit_queue)  # ex. 0, 'A'

        # 만약 방문한 노드까지의 거리가 기존 해당 노드까지의 최단거리보다 멀다면 skip
        if distances[visited_node] < visited_distance:  # ex. 0 < 0 은 False 이므로 다음 로직 진행
            continue

        # 현재 방문한 노드에서 가장 가까운 노드들을 우선순위 큐에 append
        # 우선순위 큐에 정렬된 순서가 가까운 순서이기 때문에 순차적으로 방문 가능
        for destination, destination_distance in graph[visited_node].items():  # ex. 'A' -> {'B': 8, 'C': 1, 'D': 2}
            # 현재 방문한 노드를 경유하여 다음 방문 후보 노드들까지의 합산 거리 계산
            new_distance = visited_distance + destination_distance  # ex. 'B'는 0 + 8, 'C'는 0 + 1, 'D'는 0 + 2 순서
            
            # 방문 후보 노드에 대한 기존 거리와, 경유지를 거칠 경우 합산된 거리 간 비교
            # 가중치에 따라 경유하는 상황이 더 가까운 거리일 수 있음
            if new_distance < distances[destination]:  # ex. 8 < INF True 이므로 갱신됨
                # 만약 경유지 합산 거리가 더 가깝다면 방문할 노드까지의 최단거리를 그것으로 갱신
                distances[destination] = new_distance

                # 갱신된 최단경로이므로 우선순위 큐에 다음 방문할 노드로 append
                # 만약 합산 거리가 기존보다 더 멀다면 append 하지 않아도 됨
                # 방문한다 해도 어차피 유의미한 최단거리가 될 수 없기 때문
                #     - ex. [8, 'B'], [1, 'C'], [2, 'D'] 순으로 삽입되나,
                #     - 우선순위 큐의 특성에 따라 각 0번 인덱스 값으로 정렬됨. C -> D -> B
                heapq.heappush(visit_queue, [new_distance, destination])
    return distances

>>> graph = {
...     'A': {'B': 8, 'C': 1, 'D': 2},
...     'B': {},
...     'C': {'B': 5, 'D': 2},
...     'D': {'E': 3, 'F': 5},
...     'E': {'F': 1},
...     'F': {'A': 5}
... }

>>> print(solution(graph=graph, start_node='A'))

{'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}