Флойд - 1

Повний орієнтовний зважений граф задано матрицею суміжності. Побудуйте матрицю найкоротших шляхів між усіма парами його вершин. Гарантується, що у графі немає циклів від'ємної ваги.

Вхідні дані

У першому рядку записана кількість вершин графа $n(1\le n\le 100)$. У наступних $n$ рядках записано по $n$ чисел — матриця суміжності графа ($j$-те число в $i$-ому рядку відповідає вазі ребра з вершини $i$ у вершину $j$). Всі числа за модулем не перевищують $100$. На головній діагоналі матриці знаходяться нулі.

Вихідні дані

Виведіть $n$ рядків по $n$ чисел — матрицю найкоротших відстаней між парами вершин. $j$-те число у $i$-ому рядку повинно бути рівним вазі найкоротшого шляху з вершини $i$ у вершину $j$.

Приклади