#include <iostream>
#include <fstream>
#include <stdio.h>
#include <cstring>
#define inf 10000
using namespace std;
ifstream in("royfloyd.in");
ofstream out("royfloyd.out");
int n,m,c[101][101],d[101][101],urm[101][101],i,j,maxi[101][101];
void citire()
{   int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            in>>c[i][j];
}
void initd()
{
    int i,j;
    for(i=1;i<=n;i++)
    {   for(j=1;j<=n;j++)
            {d[i][j]=inf; maxi[i][j]=1;}
        d[i][i]=0;
        maxi[i][i]=0;
    }
}
void floyd()
{
    int i,j,k;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(c[i][j]!=0 && c[i][j]!=inf)
                urm[i][j]=j;
                else urm[i][j]=0;
    memcpy(d,c,sizeof(c));
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if (d[i][j]==d[i][k]+d[k][j])
                {
                    maxi[i][j]=max(maxi[i][j],maxi[i][k]+maxi[k][j]);
                }
                else if (d[i][j]>d[i][k]+d[k][j])
                {
                    d[i][j]=d[i][k]+d[k][j];
                    urm[i][j]=urm[i][k];
                    maxi[i][j]=maxi[i][k]+maxi[k][j];
                }
}
void drum(int i, int j)
{
    printf("%d",i);
    if(i!=j)
        drum(urm[i][j],j);
        else return;
}
int main()
{
    in>>n;
    citire();
    initd();
    floyd();
    for(i=1;i<=n;i++)
        {for(j=1;j<=n;j++)
            out<<d[i][j]<<' ';
        out<<'\n';}
    //out<<'\n';
    //for(i=1;i<=n;i++)
        //{for(j=1;j<=n;j++)
            //out<<maxi[i][j]<<' ';
       // out<<'\n';}
    return 0;
}