Floyd-Warshall Delivery Routes

You are given a city map with n intersections (numbered from 1 to n) and m bidirectional roads connecting some intersections. Each road is represented by three integers u, v, and w where u and v are the intersections connected by this road and w is the time required to traverse this road.

Your task is to compute the minimum travel time between every pair of intersections using the Floyd-Warshall algorithm. If an intersection cannot be reached from another, output -1 for that pair. The algorithm should compute the shortest paths considering roads might be used multiple times.

The answer matrix will be an n x n grid where the element at the i-th row and j-th column represents the minimum time required to travel from intersection i to intersection j.

Note: Input is read from stdin and output should be printed to stdout. All road time lengths and outputs are non-negative integers.

inputFormat

The first line contains two space-separated integers n and m representing the number of intersections and the number of roads, respectively.

The next m lines each contain three space-separated integers u, v, w representing a bidirectional road between intersections u and v that takes w time to traverse.

outputFormat

Print n lines, each line containing n space-separated integers. The j-th integer in the i-th line should be the minimum time required to travel from intersection i to intersection j. If there is no path between intersections i and j, print -1 instead.

## sample

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

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

</p>