#include <iostream>
#include <fstream>

using namespace std;

ifstream in("royfloyd.in");
ofstream out("royfloyd.out");

int MatrixDimension;

int Matrix[1000][1000], DistanceMatrix[1000][1000];

void ReadMatrix(int MatrixDimension)
{
    for(int line = 1; line <= MatrixDimension; line++)
    {
        for(int column = 1; column <= MatrixDimension; column++)
        {
            in>>Matrix[line][column];
        }
    }
}

void RoyFloydAlgorithm(int n)
{
    int i, j, k;
    // n = MatrixDimensions
    // k = throughNode
    // i = startNode
    // j = destinationNode

	for (k = 1; k <= n; k++)
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				if (Matrix[i][k] && Matrix[k][j] && (Matrix[i][j] > Matrix[i][k] + Matrix[k][j] || !Matrix[i][j]) && i != j) Matrix[i][j] = Matrix[i][k] + Matrix[k][j];
}

void ShowMatrix(int MatrixDimension)
{
    for(int line = 1; line <= MatrixDimension; line++)
    {
        for(int column = 1; column <= MatrixDimension; column++)
        {
            out<<Matrix[line][column]<<" ";
        }
        out<<'\n';
    }
}

int main()
{
    in>>MatrixDimension;
    ReadMatrix(MatrixDimension);
    RoyFloydAlgorithm(MatrixDimension);
    ShowMatrix(MatrixDimension);
    return 0;
}