#! /usr/bin/python3
import priority_queue
from collections import namedtuple
import time
import sys

Edge = namedtuple('Edge', ['vertex', 'weight'])


class Graph(object):
    def __init__(self, vertex_count):
        self.vertex_count = vertex_count
        self.adjacency_list = [[] for _ in range(vertex_count)]

    def add_edge(self, source, destination, weight):
        assert source < self.vertex_count
        assert destination < self.vertex_count
        self.adjacency_list[source].append(Edge(destination, weight))

        ''' To get undirected graph uncomment this'''
        # self.adjacency_list[destination].append(Edge(source, weight))
        ''' ~~~~~~~~~~~~~~~~ :--) ~~~~~~~~~~~~~~~~~'''

    def get_edge(self, vertex):
        for e in self.adjacency_list[vertex]:
            yield e

    def get_vertex(self):
        for v in range(self.vertex_count):
            yield v


def dijkstra(graph, source, destination):
    q = priority_queue.PriorityQueue([])
    parents = []
    distances = []
    start_weight = float("inf")

    for i in graph.get_vertex():
        weight = start_weight
        if source == i:
            weight = 0
        distances.append(weight)
        parents.append(None)

    q.insert(source, 0)

    while not q.empty():
        v_tuple = q.pop(1)
        v = v_tuple.label

        if v_tuple.priority == float("inf"):
            return float("inf"), float("inf")

        for e in graph.get_edge(v):

            candidate_distance = distances[v] + e.weight
            if distances[e.vertex] > candidate_distance:
                distances[e.vertex] = candidate_distance
                parents[e.vertex] = v
                q.insert(e.vertex, distances[e.vertex])

    shortest_path = []
    ending = destination
    while ending is not None:
        shortest_path.append(ending)
        ending = parents[ending]

    shortest_path.reverse()

    return shortest_path, distances[destination]

# g = Graph(n) gdzie n --> ilość wierzchołków
# g.add_edge(start, end, cost)