// InfoArena_RoyFloyd.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

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

using namespace std;

const int INF = 100000; // În cazul în care nu avem niciun drum

int main() {
    ifstream input("royfloyd.in");  // Deschide fișierul de intrare
    ofstream output("royfloyd.out"); // Deschide fișierul de ieșire

    int n;
    cin >> n;  // Citește numărul de noduri din fișier

    vector<vector<int>> cost(n, vector<int>(n)); // Inițializăm matricea costurilor

    for (int i = 0; i < n; ++i) {  // Citim matricea costurilor din fișier
        for (int j = 0; j < n; ++j) {
            cin >> cost[i][j];
            if (i != j && cost[i][j] == 0) { // Punem INF în loc de 0 pentru elementele non-diagonale fără muchii
                cost[i][j] = INF;
            }
        }
    }

    // Aplică algoritmul Roy-Floyd
    for (int k = 0; k < n; ++k) { // Nod intermediar
        for (int i = 0; i < n; ++i) { // Nod de start
            for (int j = 0; j < n; ++j) { // Nod de destinație
                if (cost[i][k] < INF && cost[k][j] < INF) { // Dacă există drumuri valide prin `k`, actualizează costul
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
                }
            }
        }
    }

    // Scrie matricea rezultată în fișierul de ieșire
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (cost[i][j] == INF) {  // Dacă drumul este încă INF, setează-l înapoi la 0
                output << 0 << " ";
            }
            else {
                output << cost[i][j] << " ";
            }
        }
        output << "\n";  // Linie nouă pentru fiecare rând
    }

    return 0;
}


// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file