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