#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++)
        rootDistance[i][j] = rootGraph[i][j];

    for(i=0; i<N; i++){
        for(j=0; j<N; j++) fprintf(stdout,"%d ",rootDistance[i][j]);
        fprintf(stdout,"\n");
    }

        fprintf(stdout,"\n");

    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++) fprintf(file,"%d ",rootDistance[i][j]);
        fprintf(file,"\n");
    }
    fclose(file);
    return;
}