// RoyFloyd - O(N^3)
// D[i][j]= lungimea drumului minim de la i la j
// last[i][j] = ultimul nod de pe drumul minim de la i la j
// i - ...- last[i][j]-j
#include <fstream>
#define Nmax 110
using namespace std;
ifstream f("royfloyd.in");
ofstream g("royfloyd.out");

int n,d[Nmax][Nmax],last[Nmax][Nmax];

void ReadInput()
{
     int m;
    f>>n;//>>m;
    //for(int i=1;i<=m;++i)
    //{
    //     int x,y,c;
    //     f>>x>>y>>c;
    //     d[x][y]=d[y][x]=c;
    //     last[x][y]=x,last[y][x]=y;
    //}
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)f>>d[i][j];
     //for(int i=1;i<=n;++i)
        //for(int j=i;j<=n;++j)last[i][j]=i,last[j][i]=j;
}

void RoyFloyd(int d[Nmax][Nmax],int last[Nmax][Nmax])
{
    for(int k=1;k<=n;k++)
     for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        if(i!=j && d[i][k] && d[k][j] && (!d[i][j] || d[i][k]+d[k][j]<d[i][j]))
            d[i][j]=d[i][k]+d[k][j],last[i][j]=last[k][j];
}

void PrintOutput(int d[Nmax][Nmax])
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)g<<d[i][j]<<' ';
        g<<'\n';
    }
}
void BuildPath(int S, int F)
{
     if(S==F)
     {
          g<<S<<' ';
          return;
     }
     BuildPath(S,last[S][F]);
     g<<F<<' ';
}
int main()
{
    ReadInput();
    RoyFloyd(d,last);
    PrintOutput(d);
    //PrintOutput(last);
    //for(int i=1;i<=n;i++)
      //for(int j=1;j<=n;j++){g<<"path "<<i<<' '<<j<<":: "; BuildPath(i,j); g<<'\n';}
    f.close();g.close();
    return 0;
}