Write FloydWarshall. Read n m and m directed edges u v weight, then pairs a b until the end of input. Compute the shortest distance between every pair of vertices with three nested loops: for k = 0 … n − 1, allow k as an intermediate vertex — dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Maintain next[i][j], the vertex that follows i on a shortest path to j, to rebuild routes.
Print the distance matrix (width 5, - when there is no route) and, for each pair, the distance and the route (no route if none).
For the input
4 6
0 1 5
0 3 10
1 2 3
2 3 1
3 0 2
1 3 9
0 3 3 1 2 0
the program prints
Distance matrix:
0 5 8 9
6 0 3 4
3 8 0 1
2 7 10 0
0 to 3: 9 via 0 1 2 3
3 to 1: 7 via 3 0 1
2 to 0: 3 via 2 3 0