// https://www.infoarena.ro/problema/royfloyd - Szucs Patrik - Kevin
#include <fstream>
#include <climits>

int main()
{
    int n;

    std::ifstream in("royfloyd.in");
    in >> n;

    int **mtrx = new int *[n];
    for (int i = 0; i < n; i++)
    {
        mtrx[i] = new int[n];
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            in >> mtrx[i][j];
            if (mtrx[i][j] == 0 && i != j)
            {
                mtrx[i][j] = INT_MAX;
            }
        }

    in.close();

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                if (mtrx[j][k] > mtrx[j][i] + mtrx[i][k] && mtrx[i][k] != INT_MAX && mtrx[j][i] != INT_MAX)
                    mtrx[j][k] = mtrx[j][i] + mtrx[i][k];

    std::ofstream out("royfloyd.out");
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            out << mtrx[i][j] << ' ';
        }
        out << '\n';
    }
    out.close();

    for (int i = 0; i < n; i++)
    {
        delete[] mtrx[i];
    }
    delete[] mtrx;

    return 0;
}