#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

class graf {

protected:
    int noduri, muchii;
    vector < vector < int >> adiacenta;

public:
    // Constructor cu matrice de adiacenta data
    graf(vector < vector < int >> listaAdiacenta, int noduri, int muchii): adiacenta(listaAdiacenta), noduri(noduri), muchii(muchii) {};

    // Constructor fara matrice de adiacenta, se cu initalizeaza una goala
    graf(int noduri, int muchii): adiacenta(noduri + 1), noduri(noduri), muchii(muchii) {};

    vector < int > bfs(int);
    int dfs();

};

class graf_orientat : public graf{
private:
    void dfsCtc(int, vector < int >&, vector < int >&, stack < int >&, int&, vector < string >&, unordered_set < int >&);
    void dfsSortaret(int, vector < int >&, vector < int >&);

public:
    graf_orientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf(listaAdiacenta, noduri, muchii) {};
    graf_orientat(int noduri, int muchii): graf(noduri, muchii) {};

    friend istream& operator>>(istream&, graf_orientat&);

    vector < string > ctc();

    vector < int > sortaret();
};

// Clasa pentru graf orientat ponderat
class graf_orientat_ponderat : public graf_orientat {
    // Matrice de adianceta care contine si costurile
    vector< vector< pair< int, int >>> adiacentap;
public:
    graf_orientat_ponderat(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf_orientat(listaAdiacenta, noduri, muchii) {};
    graf_orientat_ponderat(int noduri, int muchii): adiacentap(noduri+1), graf_orientat(noduri, muchii) {};

    friend istream& operator>>(istream&, graf_orientat_ponderat&);

    vector<vector<int>> royfloyd(vector<vector<int>>);

};


istream& operator>>(istream& in, graf_orientat_ponderat& g) {
    for (int i = 0; i < g.muchii; i++) {
        int aux1, aux2, aux3;
        in >> aux1 >> aux2 >> aux3;
        g.adiacentap[aux1].push_back(make_pair(aux2, aux3));
    }
    return in;
}

vector<vector<int>> graf_orientat_ponderat :: royfloyd(vector<vector<int>> rasp){

    for(int k = 1; k <= noduri; k++){
        for(int i = 1; i <= noduri; i++){
            for(int j = 1; j <= noduri; j++){
                if ((rasp[i][k] + rasp[k][j] < rasp[i][j] || rasp[i][j] == 0) && rasp[k][j] && rasp[i][k] && i != j){
                    rasp[i][j] = rasp[i][k] + rasp[k][j];
                }
            }
        }
    }

    return rasp;
}

void royfloydDriver() {
    // https://infoarena.ro/problema/royfloyd
    // Citire
    ifstream in ("royfloyd.in");
    ofstream out("royfloyd.out");

    int n, m = 0;
    in >> n;

    vector<vector<int>> matrix(n+1, vector<int>(n+1));

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            in >> matrix[i][j];
        }
    }

    graf_orientat_ponderat x(n, m);
    vector<vector<int>> rasp = x.royfloyd(matrix);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            out << rasp[i][j] << " ";
        }
        out << '\n';
    }
}

int main() {
    // Se apeleaza functia corespunzatoare problemei
    royfloydDriver();
    return 0;
}