Повний орієнтований граф заданий матрицею суміжності. (В рядку \(i\) , стопвчику \(j\) міститься відстань від вершини \(i\) до вершини \(j\))
Гарантується, що в графі немає циклів від'ємної ваги.

Побудуйте матрицю найкоротших шляхів між його вершинами (щоб в рядку \(i\) , стопвчику \(j\) містилась довжина найкоротшого шляху від вершини \(i\) до вершини \(j\))

Формат вхідних даних

В першому рядку число \(N\) (\(1 \le N \le 100\)) - кількість вершин графа. В наступних \(N\) рядках міститься по \(N\) чисел - матриця суміжності графа.
Всі числа лежать в межах від -100 до 100. На головній діагоналі завжди нулі.

Формат вихідних даних

Виведіть \(N\) рядків по \(N\) чисел - матрицю найкоротших відстаней між парами вершин.

Приклад вхідних даних

4
0 5 9 100
100 0 2 8
100 100 0 7
4 100 100 0

Приклад вихідних даних

0 5 7 13 
12 0 2 8 
11 16 0 7 
4 9 11 0