#include<cstdio>
const int M=2000000;
int d[101][101],t,l;
char n,i,j,k,p[M];
inline int A()
{
  	int s=0;
  	for(;p[t]<48;t++);
  	for(;p[t]>47;t++)
  		s=s*10+p[t]-48;
  	return s;
}
inline void S(int x)
{
    int i,d=x>999?4:x>99?3:x>9?2:1;
    for(i=d-1;i>=0;x/=10,i--)
        p[l+i]=x%10+48;
    p[l+d]=32,l+=d+1;
}
int main()
{
    freopen("royfloyd.in","r",stdin),freopen("royfloyd.out","w",stdout),fread(p,1,M,stdin),n=A();
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            d[i][j]=A();
    for(k=0;k<n;k++)
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                if(i!=j&&d[i][k]&&d[k][j]&&(!d[i][j]||d[i][j]>d[i][k]+d[k][j]))
                    d[i][j]=d[i][k]+d[k][j];
    for(k=i=0;i<n;i++,p[l++]=10)
        for(j=0;j<n;j++)
            S(d[i][j]);
    fwrite(p,1,l,stdout);
}