#include <bits/stdc++.h>
using namespace std;

void citire(vector<vector<int>> &matrice)
{
    ifstream fin("royfloyd.in");
    int N;
    fin >> N;

    matrice.resize(N+1);
    for (int i = 1; i <= N; ++i){
        matrice[i].resize(N+1);
        for (int j = 1; j <= N; j++) {
            int c;
            fin >> c;
            matrice[i][j] = c;
        }
    }
}

vector<vector<int>> royFloyd(vector<vector<int>> matrice, const int costMaxim)
{
    vector<vector<int>> distante = matrice;
    //initializare matrice distante
    for (int i = 1; i <  distante.size(); ++i) {
        for (int j = 1; j < distante.size(); j++) {
            if(!matrice[i][j] && i != j) {
                distante[i][j] = costMaxim;
            }
        }
    }

    //calculare distante
    for (int k = 1; k < distante.size(); k++) {
        for (int i = 1; i < distante.size(); i++) {
             for (int j = 1; j < distante.size(); j++) {
                 if (distante[i][j] > distante[i][k] + distante[k][j] && i!=j) {
                                distante[i][j] =   distante[i][k] + distante[k][j];
                 }
            }
        }
    }

    return distante;
}


void afisare(vector<vector<int>> matrice)
{
    ofstream fout("royfloyd.out");
    for(int i = 1; i < matrice.size(); ++i) {
        for (int j = 1; j < matrice.size(); ++j) {
            fout << matrice[i][j] << " ";
        }
        fout << "\n";
    }
}

int main()
{
    vector<vector<int>> matrice;
    citire(matrice);

    vector<vector<int>> distante;
    distante = royFloyd(matrice, 1005);
    afisare(distante);
    return 0;
}