/*
    Supr*
    All pairs shortest path - Pseudo Multiply O(V^3*log(V))
*/
#include <fstream>
#define NMAX 105 //maximum num of nodes
#define INF 1e9 //infinity
#define MIN(A, B) A <= B ? A : B //min function
using namespace std;
 
ifstream f("royfloyd.in"); //in file
ofstream g("royfloyd.in.out"); //out file
 
int graph[NMAX][NMAX];  //our graph
int lMatrix[NMAX][NMAX]; //result graph
int tmpMatrix[NMAX][NMAX]; //temporary graph
int V;
 
void read_data(int& V){
    f >> V; //num of vertices
    for(int i = 1; i<=V; i++){
        for(int j = 1; j<=V; j++){
            f >> graph[i][j];       //read graph from file
            lMatrix[i][j] = graph[i][j];
        }
    }
}
 
void initMatrix(int matrix[][NMAX]){
    for(int i = 1; i<=V; i++){      //initialize temporary matrix with infinity
        for(int j = 1; j<=V; j++){
            matrix[i][j] = INF;
        }
    }
}
 
void extendShortestPath(int lMatrix[][NMAX], int graph[][NMAX], int tmpMatrix[][NMAX]){
    initMatrix(tmpMatrix);
    for(int i = 1; i<=V; i++){
        for(int j = 1; j<=V; j++){
            for(int k = 1; k<=V; k++){
                tmpMatrix[i][j] = MIN(tmpMatrix[i][j], lMatrix[i][k] + graph[k][j]);    //applying dp for matrix mul
            }
        }
    }
 
    for(int i = 1; i<=V; i++){
        for(int j = 1; j<=V; j++){
            lMatrix[i][j] = tmpMatrix[i][j];
        }
    }
}
 
void shortestMatMul(int graph[][NMAX]){
    int m = 1;
    while(m < V){
        extendShortestPath(lMatrix, lMatrix, tmpMatrix);    //multiplying matrices in logV
        m *= 2;
    }
 
}
 
void printResult(){
    for(int i =1 ; i<=V; i++){
        for(int j = 1; j<=V; j++){
            g << lMatrix[i][j] << ' ';
        }
        g << '\n';
    }
}
 
int main(){
    read_data(V); //read data
    shortestMatMul(graph); //calculate shortest paths
    printResult(); //print results
}