Floyd-Warshall: All-Pairs Shortest Paths

You are given N cities and M directed roads. Each road is represented by a triple (U, V, T) indicating there is a road from city U to city V with travel time T. Your task is to compute the shortest travel time between every pair of cities using the Floyd-Warshall algorithm. If there is no path from city i to city j, output INF to denote infinity.

The recurrence of the Floyd-Warshall algorithm is given by the formula: $$dist[i][j] = \min(dist[i][j],\, dist[i][k] + dist[k][j])$$ where \(dist[i][j]\) represents the current shortest distance from city \(i\) to city \(j\). Note that if there is no path, the value is considered as \(\text{INF}\) (infinity).

Implement the algorithm so that it reads input from stdin and writes the resulting matrix to stdout. Each row of the output matrix should be printed on a new line with space-separated values.

inputFormat

The first line contains two integers N and M separated by a space, where N is the number of cities and M is the number of roads.

The following M lines each contain three integers U, V, and T, representing a road from city U to city V with travel time T.

outputFormat

Output an N x N matrix where the element in the i-th row and j-th column represents the shortest travel time from city i to city j. If there is no path from city i to city j, print INF for that entry. Each row should be printed on a new line with space-separated values.

## sample

4 4
1 2 3
2 3 4
3 4 5
1 4 10

0 3 7 10
INF 0 4 9
INF INF 0 5
INF INF INF 0

</p>