#include <stdio.h>
#include <stdlib.h>
#define MAX_INT 32767

void RoyFloyd(int N, int** rootGraph, int** rootDistance);
void printOutput(int N, int** rootDistance);

int main()
{
    int N,j,i;
    int** rootGraph;
    int** rootDistance;

    FILE* file;
    file = fopen("royfloyd.in","r");
    fscanf(file,"%d",&N);


    rootGraph = (int**)malloc(N*sizeof(int*));
    for(i=0;i<N;i++) rootGraph[i] = (int*)malloc(N*sizeof(int));
    rootDistance = (int**)malloc(N*sizeof(int*));
    for(i=0;i<N;i++) rootDistance[i] = (int*)malloc(N*sizeof(int));


    for(i=0; i<N; i++)
    for(j=0; j<N; j++)
       fscanf(file,"%d",rootGraph[i]+j);

    fclose(file);

    RoyFloyd(N,rootGraph,rootDistance);
    printOutput(N,rootDistance);
    return 0;
}

void RoyFloyd(int N, int** rootGraph, int** rootDistance)
{
    int i,j,k;
    for(i=0; i<N; i++)
    for(j=0; j<N; j++)
        rootDistance[i][j] = MAX_INT;

    for(i=0; i<N; i++)
    for(j=0; j<N; j++)
        {
            if(rootGraph[i][j] != 0) rootDistance[i][j] = rootGraph[i][j];
            if(i==j) rootDistance[i][j] = 0;
        }

    for(k=0; k<N; k++){
        for(i=0; i<N; i++){
            for(j=0; j<N; j++){
                if(rootDistance[i][j] > (rootDistance[i][k] + rootDistance[k][j])) rootDistance[i][j] = rootDistance[i][k] + rootDistance[k][j];
            }}}
    return;
}

void printOutput(int N, int** rootDistance)
{
    int i,j;
    FILE* file;
    file = fopen("royfloyd.out","w");
    for(i=0; i<N; i++){
        for(j=0; j<N; j++)
        {
            if(rootDistance[i][j]!=MAX_INT)  fprintf(file,"%d ",rootDistance[i][j]);
            else  fprintf(file,"%d",0);
        }
        fprintf(file,"\n");
    }
    fclose(file);
    return;
}