Флойд - 1

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между всеми парами его вершин. Гарантируется, что в графе нет циклов отрицательного веса.

Входные данные

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

Выходные данные

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

Примеры