#include <iostream>
#include <fstream>

#define MAX 257
#define INF 100001

using namespace std;

int N,matDrumurilor[MAX][MAX],nrDrumuri[MAX][MAX];

void citire(){
    int i,j;
    ifstream f("rf.in");
    f>>N;
    for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
            f>>matDrumurilor[i][j];
            if(matDrumurilor[i][j]==0 && i!=j){
                matDrumurilor[i][j]=INF;
            }
            if(i!=j){
                nrDrumuri[i][j]=nrDrumuri[j][i]=1;
            }
        }
    }
}

void royfloyd(){
    int i,j,k;
    for(k=1;k<=N;k++){
        for(i=1;i<=N;i++){
            for(j=i+1;j<=N;j++){
                if(matDrumurilor[i][j]>matDrumurilor[i][k]+matDrumurilor[k][j]){
                    matDrumurilor[i][j]=matDrumurilor[j][i]=matDrumurilor[i][k]+matDrumurilor[k][j];
                    if(nrDrumuri[i][j]<nrDrumuri[i][k]+nrDrumuri[k][j]){
                        nrDrumuri[i][j]=nrDrumuri[j][i]=nrDrumuri[i][k]+nrDrumuri[k][j];
                    }
            }else if(matDrumurilor[i][j]==matDrumurilor[i][k]+matDrumurilor[k][j] && nrDrumuri[i][j]<nrDrumuri[i][k]+nrDrumuri[k][j]){
                nrDrumuri[i][j]=nrDrumuri[j][i]=nrDrumuri[i][k]+nrDrumuri[k][j];
            }
        }
    }
}
}
void afisare(){
    ofstream g("rf.out");
    int i,j;
    for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
            if(matDrumurilor[i][j]==INF){
                g<<0<<" ";
            }else{
                g<<matDrumurilor[i][j]<<" ";
            }
        }
        g<<"\n";
    }
    for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
                g<<nrDrumuri[i][j]<<" ";
        }
        g<<"\n";
    }

}


int main()
{
    citire();
    royfloyd();
    afisare();
    return 0;
}