#include <iostream>
#include <fstream>
using namespace std;
#define INF 99999


ofstream output;

void printMatrix(int graph[][100], int n);

void floydWarshall(int graph[][100], int n){
    int distanceMatrix[100][100], i, j, k;

    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            distanceMatrix[i][j] = graph[i][j]; //initialize the solution matrix
    
    for (k=0; k<n; k++){
        for(i=0; i<n; i++){
            for(j=0; j<n; j++){
                if(distanceMatrix[i][k] + distanceMatrix[k][j] < distanceMatrix[i][j])
                    distanceMatrix[i][j] = distanceMatrix[i][k] + distanceMatrix[k][j];
            }

        }
    }

    printMatrix(distanceMatrix, n); //print the shorthest matrix graph
}

void printMatrix(int distanceMatrix[][100], int n)  
{  

    for (int i = 0; i < n; i++)  
    {  
        for (int j = 0; j < n; j++)  
        {  
            if (distanceMatrix[i][j] == INF)  
                output<<0<<"  ";  
            else
                output<<distanceMatrix[i][j]<<"  ";  
        }  
        output<<endl;  
    }  
} 

int main(){
    int n, graph[100][100];

    ifstream input;
    input.open("royfloyd.in");
    output.open("royfloyd.out");
    input >>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
            input >> graph[i][j];
    }

    floydWarshall(graph, n);

    return 0;
}