Флойд - 1

Input

Первая строка содержит количество вершин графа n~(1 \le n \le 100). Каждая из следующих $n$ строк содержит $n$ целых чисел, описывающих матрицу смежности графа: $j$-е число в $i$-й строке равно весу ребра из вершины $i$ в вершину $j$. Абсолютная величина каждого числа не превышает $100$. Элементы главной диагонали матрицы всегда равны нулю.

Output

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

Examples