#include <bits/stdc++.h>
#define Dim 101
#define oo 1e9
using namespace std;
ifstream f("royfloyd.in");
ofstream g("royfloyd.out");
long long  N,A[2][Dim][Dim],T[2][Dim][Dim];

void Tipareste(int i,int j)
{ cout<<i<<' '<<j<<'\n';
    if(i==j) cout<<i<<' ';
    else
    {
        if(T[N%2][i][j]==-1)
            cout<<"Nu exista drum";
        else
        {
            Tipareste(i,T[N%2][i][j]);
            cout<<j<<' ';
        }
    }
}

int main()
{
    f>>N;
    for(int i=1;i<=N;i++)
    for(int j=1;j<=N;j++)
    {
        f>>A[0][i][j];

        if(i!=j && A[0][i][j]==0) A[0][i][j]=oo;

        if(i==j||A[0][i][j]==oo) T[0][i][j]=-1;
        else
        if(i!=j || A[0][i][j]<oo ) T[0][i][j]=i;
    }

    for(int k=1;k<=N;k++)
    for(int i=1;i<=N;i++)
    for(int j=1;j<=N;j++)
    if( i != j )
    if( A[!(k%2)][i][j]!=oo || (A[!(k%2)][i][k]!=oo && A[!(k%2)][k][j]!=oo) )
    {
        if( A[!(k%2)][i][j] <= A[!(k%2)][i][k]+A[!(k%2)][k][j] )
        {
            A[k%2][i][j]=A[!(k%2)][i][j];
            T[k%2][i][j]=T[!(k%2)][i][j];
        }
        else
        {
            A[k%2][i][j]=A[!(k%2)][i][k]+A[!(k%2)][k][j];
            T[k%2][i][j]=T[!(k%2)][k][j];
        }
       //cout<<k<<' '<<i<<' '<<j<<' '<<' '<<A[k%2][i][j]<<' '<<A[!(k%2)][i][j]<<' '<<A[!(k%2)][i][k]<<' '<<A[!(k%2)][k][j]<<'\n';
    }
    else
    if(i!=j)
    {
        A[k%2][i][j]=oo;
        T[k%2][i][j]=-1;
    }

    //cout<<"Matricea drumurilor minime intre oricare doua perechi de varfuri este: "<<'\n';
    for(int i=1;i<=N;i++,g<<'\n')
    for(int j=1;j<=N;j++)
    if( A[N%2][i][j] == oo ) g<<0<<' ';
    else g<<A[N%2][i][j]<<' ';
 return 0;
    bool ok;
    cout<<"Doresti sa tiparesti un drum? "; cin>>ok;cout<<'\n';
    while(ok)
    {
        int u,v;
        cout<<"Alege cele doua noduri "<<'\n'; cin>>u>>v;
        Tipareste(u,v);
        cout<<'\n';
        cout<<"Doresti sa tiparesti un drum? "; cin>>ok;cout<<'\n';
        if(ok) cout<<'\n';
    }

    return 0;
}