from queue import PriorityQueue
from collections import defaultdict

def network_delay_time(times, n, k):
    adjacency = defaultdict(list)
    for src, dst, t in times:
        adjacency[src].append((dst, t)) 

    pq = PriorityQueue()
    pq.put((0, k)) 
    visited = set() 
    delays = 0   
      
    while not pq.empty():
        time, node = pq.get()
      
        if node in visited:
            continue
          
        visited.add(node)  
        delays = max(delays, time) 
        neighbours = adjacency[node]

        for neighbour in neighbours:
            neighbour_node, neighbour_time = neighbour
            if neighbour_node not in visited:
                new_time =  time + neighbour_time
                pq.put((new_time, neighbour_node))
  
    if len(visited) == n:
        return delays

    return -1


# Driver code
def main():
    time = [
                [[2, 1, 1], [3, 2, 1], [3, 4, 2]],
                [[2, 1, 1], [1, 3, 1], [3, 4, 2], [5, 4, 2]],
                [[1, 2, 1], [2, 3, 1], [3, 4, 1]],
                [[1, 2, 1], [2, 3, 1], [3, 5, 2]],
                [[1, 2, 2]]
            ]

    n = [4, 5, 4, 5, 2]
    k = [3, 1, 1, 1, 2]

    for i in range(len(time)):
        print(i + 1, ".\t times = ", time[i], sep="")
        print("\t number of nodes 'n' = ", n[i], sep="")
        print("\t starting node 'k' = ", k[i], "\n", sep="")
        print("\t Minimum amount of time required = ", network_delay_time(time[i], n[i], k[i]), sep="")
        print("-" * 100)


if __name__ == "__main__":
    main()