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

/*
        Algoritmul Floyd-Warshall
*/

#define INF (1 << 20)
#define NO_PARENT -1
class Task {
public:
    void solve() {
        read_input();
        get_result();
        print_solution();
    }
private:
    int n;

    // matricea costrutilor
    vector<vector<int>> dist;

    // matrice care va contine parintele nodului j in drumul minim catre i
    vector<vector<int>> p;

    void read_input() {
        ifstream fin("royfloyd.in");

        // citesc numarul de noduri
        fin >> n;

        dist.resize(n + 1);
        p.resize(n + 1);
        
        // construiesc matricea de costuri
        for (int i = 1; i <= n; ++i) {
            dist[i].resize(n + 1);
            p[i].resize(n + 1);
            for (int j = 1; j <= n; ++j) {
                int cost;

                // citesc costul muchiei (i -> j)
                fin >> cost;
                if (cost == 0) {
                    // nu exista drum direct i -> j
                    dist[i][j] = INF;

                    // j nu are parinte in drumul direct i -> j
                    p[i][j] = NO_PARENT;

                    continue;
                }

                // adaug in matricea costurilor si marchez nodul i ca parinte al lui j
                dist[i][j] = cost;
                p[i][j] = i;
            }
        }

        fin.close();
    }

    void get_result() {
        FloyWarshall(dist, p);
    }

    void FloyWarshall(vector<vector<int>> &dist, vector<vector<int>> &p) {

        for (int k = 1; k <= n; ++k) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {

                    if (i != j && dist[i][j] > dist[i][k] + dist[k][j]) {
                        // fac update la distanta folosindu-ma de distanta de i -> k si k -> j
                        dist[i][j] = dist[i][k] + dist[k][j];

                        // noul parinte al lui j este parintele lui j de pe drumul minim k -> j
                        p[i][j] = p[k][j];
                    }
                }
            }
        }
    }
    

    // returneaza vector de pathuri pentru drumuri (i, j)
    vector<vector<int>> reconstruct_paths(vector<vector<int>> &p) {
        vector<vector<int>> paths;
        vector<int> path;
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                path.clear();

                // daca nodul destinatie coincide cu nodul sursa
                if (i == j) {
                    // introducem vector gol in vectorul de paths
                    paths.push_back(path);

                    continue;
                }

                int node = j;

                for (; node != INF; node = p[i][node]) {
                    path.push_back(node);
                }

                reverse(path.begin(), path.end());

                paths.push_back(path);
            }
        }

        return paths;
    }

    void show_paths() {
        vector<vector<int>> paths = reconstruct_paths(p);
        
        int k = -1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                ++k;
                if (paths[k].size() == 0) {
                    continue;
                }

                cout << i << " -> " << j << ": ";
                for (auto &it : paths[k]) {
                    cout << it << " ";
                }
                cout << endl;
            }
        }
    }

    void print_solution() {
        ofstream fout("royfloyd.out");

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][j] == INF) {
                    fout << 0 << " ";
                    continue;
                }

                fout << dist[i][j] << " ";
            }
            fout << endl;
        }

        // show_paths();
        fout.close();
    }
};

int main() {
    Task *task = new Task();
    task->solve();
    delete task;

    return 0;
}