import math
import collections
from heapq import *

class Node:
    def __init__(self, id):
        self.id = id
        self.edges = []

    def add_route(self, to, cost):
        self.edges.append({
            "to": to,
            "cost": cost
        })

    def __lt__(self, t):
        return True


def dijkstra(nodes):
    start = nodes[0]
    end = nodes[-1]

    distance_from_start = {n: math.inf for n in nodes}
    distance_from_start[start] = 0

    minHeap = []
    heappush(minHeap, (0, start))

    while minHeap:
        (distance, current) = heappop(minHeap)

        if distance_from_start[current] < distance:
            continue

        for edge in current.edges:
            cost = edge["cost"]
            to = edge["to"]

            if cost + distance_from_start[current] < distance_from_start[to]:
                distance_from_start[to] = cost + distance_from_start[current]
                heappush(minHeap, (cost + distance_from_start[current], to))
    
    return distance_from_start[end]

def add_node(f, to, weight):
    f.add_route(to, weight)

def main():
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)
    node5 = Node(5)
    node6 = Node(6)
    node7 = Node(7)

    add_node(node1, node2, 10)
    add_node(node1, node3, 16)
    add_node(node1, node4, 12)
    add_node(node2, node3, 18)
    add_node(node2, node5, 4)
    add_node(node4, node3, 3)
    add_node(node3, node6, 1)
    add_node(node6, node7, 9)
    add_node(node5, node7, 21)

    dist = dijkstra([node1, node2, node3, node4, node5, node6, node7])

    print(dist)


main()