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

void citire(std::vector<std::vector<int> > &d, int &n) {
    int x;
    std::ifstream f("royfloyd.in");
    f >> n;
    d.assign(n, std::vector<int>(n));
    // pred.assign(n, std::vector(n, INT_MAX));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            f >> x;
            if (x == 0)
                d[i][j] = INT_MAX;
            else
                d[i][j] = x;
            // pred[u - 1][v - 1] = u - 1;
        }
    f.close();
}

void print(std::vector<std::vector<int> > &d, const int n) {
    std::ofstream g("royfloyd.out");
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (d[i][j] == INT_MAX || i == j)
                g << 0 << " ";
            else
                g << d[i][j] << " ";
        }
        g << "\n";
    }
}

void floydWarshall() {
    std::vector<std::vector<int> > d;
    // std::vector<std::vector<int> > pred;
    int n;
    citire(d, n);

    for (int k = 0; k < n; ++k) // pasul K (in total sunt N pasi)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (d[i][k] != INT_MAX && d[k][j] != INT_MAX && d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    // pred[i][j] = pred[k][j];
                }
    // for (int i = 0; i < n; ++i)
    // if (d[i][i] < 0) {
    // std::cout << "Exista un circuit negativ";
    // return;
    // }
    print(d, n);
}

int main() {
    // CERINTA: Se da un graf orientat ponderat cu ponderi reale. Pentru oricare 2 varfuri, sa se determine distanta
    // minima si un drum minim.

    // Pasul 1: matricea de distanta D va avea elemente de tip D[i][j], care reprezinta (la pasul K) distanta minima de
    // la i la j utilizand ca varfuri intermediare doar varfuri din multimea {1, ..., k}. De asemenea, matricea
    // pred[i][j] va retine ultimul varf intermediar dintre i si j.
    // Pasul 2: vor fi N pasi (deoarece varfurile intermediare pot fi de la 1 la N). La fiecare pas, actualizam d[i][j]
    // si pred[i][j] pentru toate perechile (i,j).

    // Complexitate: O(n^3).

    floydWarshall();
    return 0;
}