Shortest Path on a Weighted Graph

The Weighted graphs challenge demonstrated the use a Breadth-First-Search (BFS) to find the shortest path to a node by number of connections, but not by distance. When driving to a destination, you'll usually care about the actual distance between nodes. What algorithm will find the shortest total distance to each node?

Shortest Path Algorithm

BFS makes sure to always reach the points in order of distance, so every node it reaches is along the shortest path. How can you make sure to do the same on a weighted graph? Think about an algorithm you could use before clicking below.

Dijkstra Animation
You can view Dijkstra's algorithm in action here. Enter a 0 and click the button to run Dijkstra from node 0. See also Example Networks1 for a walk-through of the algorithm.

Challenge

Given a graph of input in the adjacency matrix format, can you find and print the distance from node 0 to all the nodes?

Sample Input

1
6
0 0 1 3 0 0
0 0 0 5 0 0 
1 0 0 2 1 4
3 5 2 0 7 0
0 0 1 7 0 2
0 0 4 0 2 0

Sample Output

0 8 1 3 2 4 

Explanation

The output is the shortest distance to each node in order, as shown in the middle column in the following table: