import math
import random
import heapq

class Graph:

# Assumes that the nodes are {0, 1, ..., n-1}.  'dir' is a Boolean flag
# to indicate whether it's a directed graph, or undirected (if dir is 0).
    def __init__(self,n,directed,filename):
        self.n = n
        self.adj_list = {}
        for l in range(self.n):
            self.adj_list[l] = []
        reader = open(filename,'r')
        lines = reader.readlines()
        reader.close()
        e = len(lines)
        for l in range(e):
            x = lines[l].split()
            self.adj_list[int(x[0])].append((int(x[1]),float(x[2])))
            if not directed:
                self.adj_list[int(x[1])].append((int(x[0]),float(x[2])))


    def DijkstraSimple(self,s):
        dists = [float('inf') for j in range(self.n)]
        pi = [None for j in range(self.n)]
        dists[s]=0
        S = {s}
        cont = True
        while cont:
           cont = False
           mind, minu, minv = float('inf'), s, None
           for u in S:
               for (v, w) in self.adj_list[u]:
                   if (v not in S) and (math.isinf(mind) or dists[u]+w < mind):
                       mind = dists[u]+w
                       minu = u
                       minv = v
           if minv is not None:
               S.add(minv)
               dists[minv] = mind
               pi[minv] = minu
               cont = True
        return dists, pi
                
                       

    def Dijkstra(self,s):
        dists = [float('inf') for j in range(self.n)]
        pi = [None for j in range(self.n)]
        myheap = []
        dists[s]=0
        heapq.heappush(myheap, (0, s))
        while myheap:
            dstar, u = heapq.heappop(myheap)
            for (x, wux) in self.adj_list[u]:
                dist = dstar + wux
                if math.isinf(dists[x]) or dist < dists[x]:
                    dists[x] = dist
                    pi[x]= u
                    heapq.heappush(myheap, (dist, x))
        return dists, pi

def printPath(arr, v):
    l = len(arr)
    if arr[v] == None:
        print(v,end='')
    else:
        printPath(arr, arr[v])
        print(" -> "+str(v),end='') 


def main():
    if self.adj_list is not None:
        vals, points = Dijkstra(self.adj_list,self.n)
        print("For vertex 4, path is: ") 
        printPath(vals,4)
             
if __name__ == '__main__':
    main()