Вы приехали на архипелаг Алгосы (наконец-то!). Здесь есть n достопримечательностей. Ваша лодка может высадить вас у одной из них, забрать у какой-то другой, возможно, той же самой достопримечательности и увезти на материк.
Чтобы более тщательно спланировать свой маршрут, вы хотите узнать расстояния между каждой парой достопримечательностей Алгосов. Некоторые из них соединены мостами, по которым вы можете передвигаться в любую сторону. Всего мостов m.
Есть вероятность, что карта архипелага устроена так, что нельзя добраться от какой-то одной достопримечательности до другой без использования лодки.
Найдите кратчайшие расстояния между всеми парами достопримечательностей.
В первой строке даны числа n (1 ≤ n ≤ 100) и m (0 ≤ m ≤ n (n-1)/2). В следующих m строках описаны мосты. Каждый мост задаётся номерами двух достопримечательностей 1 ≤ u, v ≤ n и длиной дороги 1 ≤ L ≤ 103.
Выведите матрицу n × n кратчайших расстояний. На пересечении i-й строки и j-го столбца должно стоять расстояние от i-й до j-й достопримечательности. Если между какой-то парой нет пути, то в соответствующей клетке поставьте -1.
|
4 4 1 2 1 2 3 3 3 4 5 1 4 2 |
0 1 4 2 1 0 3 3 4 3 0 5 2 3 5 0 |
|
3 2 1 2 1 1 2 2 |
0 1 -1 1 0 -1 -1 -1 0 |
|
2 0 |
0 -1 -1 0 |