Timmy lives in hell and is the resident water boy. Timmy must deliver water to all the houses from the well but he needs to get there in the least possible time so that the water doesn't evaporate. Modify Dijkstra's algorithm so that the paths are printed after the algorithm terminates. The graph will be connected. Timmy always start at node 0. NOTE: the graph is undirected .
There is only one test case. On the first line there will be two integers "n m", where n is the number of nodes and m is the number of edges. Nodes are numbered 0 to n-1. (0 < n <= 300, 0 < m <= 44850). m lines follow in the form "a b w" where a is the origin, b is the destination and w is the weight of the edge. The graph will be connected. (0 <= w <= 100)
Output the shortest path from node 0 to all the other nodes in the following format. Print out the nodes that the path takes, and print " -> " between those nodes. Then, print a single space and print the weight of that path.
3 3 0 1 2 1 2 1 2 0 13
0 0 0 -> 1 2 0 -> 1 -> 2 3