import heapq
import math


def path_print(source, destination, parent):
    if parent[destination] == destination:
        print(destination, end = " ")
    else:
        path_print(source, parent[destination], parent)
        print(destination, end = " ")
                  

def dijkstra(graph, source):
    v = len(graph)
    d = [math.inf] * v
    p = [None] * v
    fop = [0] * v
    
    min_heap = []
    
    d[source] = 0
    p[source] = source
    
    heapq.heappush(min_heap, (d[source], source))
    
    while len(min_heap) > 0:
        data = heapq.heappop(min_heap)
        current_node = data[1]
        
        if fop[current_node] == 1:
            continue
        
        fop[current_node] = 1
        
        
        for neighbor, cost in graph[current_node]:
            
            if fop[neighbor] == 1:
                continue
            
            if d[neighbor] > d[current_node] + cost:
                d[neighbor] = d[current_node] + cost
                p[neighbor] = current_node
                heapq.heappush(min_heap, (d[neighbor], neighbor))
    

    print(d)
    
    path_print(0, 3, p)

graph = {
    0: [(1, 2), (2, 7)],
    1: [(2, 3), (3, 17)],
    2: [(3, 5)],
    3: []
    }
dijkstra(graph, 0)