This is a shortest path in a graph with path tracking. The shortest
path can be done with Dijkstra of a simple BFS. For the path tracking
you can use an array telling you what is the predecessor of each node,
the value in this array for each node is to be updated whenever we
change the distance of the corresponding node.