#include <iostream>
#include <vector>
#include <fstream>

const int INF = 1000000000;

struct Edge {
    int x, y, c;
};

std::pair<std::vector<std::vector<int>>, std::vector<std::vector<int>>> RoyFloydWarshall(int n, std::vector<std::vector<int>> &dist) {
    std::vector<std::vector<int>> parent(n, std::vector<int>(n, -1));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == 0 && i != j) {
                dist[i][j] = INF; // Setăm la INF dacă nu există muchie
            } else if (dist[i][j] != INF) {
                parent[i][j] = i;
            }
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    parent[i][j] = parent[k][j];
                }
            }
        }
    }

    return {dist, parent};
}

int main() {
    std::ifstream fin("royfloyd.in");
    std::ofstream fout("royfloyd.out");

    int n;
    fin >> n;
    std::vector<std::vector<int>> dist(n, std::vector<int>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            fin >> dist[i][j];
        }
    }

    auto result = RoyFloydWarshall(n, dist);
    auto shortestPaths = result.first;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (shortestPaths[i][j] == INF) {
                fout << 0 << " ";  // Dacă nu există drum, afișăm 0
            } else {
                fout << shortestPaths[i][j] << " ";
            }
        }
        fout << "\n";
    }

    return 0;
}