Shortest Travel Time in a Road Network

You are given a network of cities connected by bidirectional roads. Your task is to compute the shortest travel time between every pair of cities using the Floyd-Warshall algorithm.

The input consists of two integers \(n\) and \(m\) representing the number of cities and roads respectively, followed by \(m\) lines each containing three integers \(u\), \(v\), and \(w\). Each tuple \((u, v, w)\) denotes that there is a road connecting city \(u\) and city \(v\) with a travel time of \(w\). If there is no path between two cities, the travel time should be reported as \(-1\).

Your task is to output an \(n \times n\) matrix where the element at the \(i\)-th row and \(j\)-th column represents the shortest travel time from city \(i\) to city \(j\). Use stdin for input and stdout for output.

inputFormat

The first line contains two integers \(n\) (the number of cities) and \(m\) (the number of roads).

Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\), representing a road between cities \(u\) and \(v\) with a travel time \(w\).

outputFormat

Output an \(n \times n\) matrix where the element at the \(i\)-th row and \(j\)-th column represents the shortest travel time from city \(i\) to city \(j\). If there is no route between two cities, output \(-1\) for that pair. Each row of the matrix should be printed on a new line with the values separated by spaces.

## sample

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

0 5 9 11
5 0 10 12
9 10 0 2
11 12 2 0

</p>