from queue import PriorityQueue, Queue
from typing import List, Tuple


class Vertex:

    def __init__(self, index):
        self.index = index
        self.distance = None

    def __repr__(self):
        return f"Node({self.index}): distance {self.distance}"

    def __lt__(self, other):
        return self.distance < other.distance

class Graph:

    def __init__(self, N):
        self.V = [Vertex(i) for i in range(N)]
        self.E: List[List[Tuple[Vertex, int]]] = [[] for _ in range(N)]

    def add_edge(self, u, v, d):
        self.E[u].append((self.V[v], d))
        # neorientovaný graf = hrana oběma směry
        self.E[v].append((self.V[u], d))

    def get_neighbors(self, u: Vertex) -> List[Tuple[Vertex, int]]:
        return self.E[u.index]

    def bfs(self, s: int):
        for v in self.V:
            v.distance = None

        start = self.V[s]
        start.distance = 0

        # q = Queue()
        q = PriorityQueue()
        q.put(start)

        while not q.empty():
            u = q.get()

            print(u)

            for v, d in self.get_neighbors(u):
                if v.distance is None:
                    v.distance = u.distance + d
                    q.put(v)
                elif v.distance > u.distance + d:
                    v.distance = u.distance + d

if __name__ == '__main__':

    G = Graph(3)
    G.add_edge(0, 1, 3)
    G.add_edge(0, 2, 1)
    G.add_edge(2, 1, 1)

    G.bfs(0)