Floyd-Warshall: Shortest Paths in a Cave System

In this problem, a group of archaeologists is exploring a newly discovered cave system. The cave consists of n chambers connected by m bidirectional tunnels, each having a positive length.

The task is to compute the shortest path between every pair of chambers using the Floyd–Warshall algorithm. Here, \(1 \le n \le 1000\) and \(0 \le m \le \frac{n(n-1)}{2}\). If there is no path between two chambers, output \(-1\) for that pair. Note that the distance from any chamber to itself is always \(0\).

inputFormat

The first line contains two integers n and m — the number of chambers and tunnels respectively.

Each of the next m lines contains three integers u, v and w, representing a tunnel connecting chambers u and v with length w.

outputFormat

Output an n x n matrix, where the element in the i-th row and j-th column is the length of the shortest path from chamber i to chamber j. If there is no path, output -1 for that position.

## sample

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

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

</p>