#include <bits/stdc++.h>

using namespace std;

// ifstream in("IO/citire.in");

// ifstream in("roy-floyd.in");
// ofstream cout("roy-floyd.out");

ifstream in("royfloyd.in");
ofstream out("royfloyd.out");

const int infinity = numeric_limits<int>::max();
// muchie de la x la y cu costul cost
struct Muchie
{
    int x, y;
    int cost = 0;

    Muchie() = default;

    Muchie(int x, int y, int cost)
    {
        this->x = x;
        this->y = y;
        this->cost = cost;
    }
};

// nodul x are in lista de adiacenta un Nod cu nod=y si costul = 10
// daca avem muchie de la x la y cu costul 10
struct Nod
{
    int nod;
    int cost = 0;

    Nod() = default;
    Nod(int nod) { this->nod = nod; }
    Nod(int nod, int cost)
    {
        this->nod = nod;
        this->cost = cost;
    }
};

class Graf
{
public:
    int nrNoduri;
    int nrMuchii;
    vector<bool> vizitat;
    vector<int> grad_intern;
    vector<int> grad_extern;
    vector<vector<Nod>> lista_adiacenta;
    vector<Muchie> muchii;

    Graf() = default;

    Graf(int nrNoduri)
    {
        this->nrNoduri = nrNoduri;
        vizitat.resize(nrNoduri + 1);
        grad_intern.resize(nrNoduri + 1, 0);
        grad_extern.resize(nrNoduri + 1, 0);
        lista_adiacenta.resize(nrNoduri + 1);
    }
    Graf(int nrNoduri, int nrMuchii)
    {
        this->nrMuchii = nrMuchii;
        this->nrNoduri = nrNoduri;
        vizitat.resize(nrNoduri + 1);
        grad_intern.resize(nrNoduri + 1, 0);
        grad_extern.resize(nrNoduri + 1, 0);
        lista_adiacenta.resize(nrNoduri + 1);
    }

    void calculeazaGrad()
    {
        for (int nod = 1; nod <= nrNoduri; nod++)
        {
            for (auto vecin : lista_adiacenta[nod])
            {
                grad_intern[vecin.nod] += 1;
                grad_extern[nod] += 1;
            }
        }
    }

    void dfs(int start, stack<int> &stiva)
    {
        vizitat[start] = true;
        for (auto vecin : lista_adiacenta[start])
        {
            if (vizitat[vecin.nod] == false)
            {
                dfs(vecin.nod, stiva);
            }
        }
        stiva.push(start);
    }

    vector<int> sortareTopologica()
    {
        vector<int> noduri_start;
        stack<int> stiva;
        for (int nod = 1; nod <= nrNoduri; nod++)
        {
            if (grad_intern[nod] == 0)
            {
                noduri_start.push_back(nod);
            }
        }

        for (auto nod : noduri_start)
        {
            dfs(nod, stiva);
        }

        vector<int> sortaretopologica;
        while (!stiva.empty())
        {
            sortaretopologica.push_back(stiva.top());
            stiva.pop();
        }

        return sortaretopologica;
    }

    void printGraf()
    {
        for (int i = 1; i <= nrNoduri; i++)
        {
            cout << i << ": ";
            for (auto nod : lista_adiacenta[i])
                cout << nod.nod << "(" << nod.cost << ") ";
            cout << endl;
        }
    }

    void printGrad()
    {
        for (int i = 1; i <= nrNoduri; i++)
        {
            cout << i << "-> grad intern = " << grad_intern[i] << ", grad extern = " << grad_extern[i] << endl;
        }
    }

    // drumul de cost maxim pentru graf orientat/neorientat aciclic de sursa si final unic
    // costul maxim  = drum[end]
    // drumul se obtine de la end pana ajungem la sursa prin vectorul de tati
    void drumCritic(int sursa, vector<int> &drum, vector<int> &tata)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = -1;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        vector<int> top = sortareTopologica();
        for (auto nod : top)
        {
            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] + vecin.cost > drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    tata[vecin.nod] = nod;
                }
            }
        }
    }

    void Djikstra(int sursa, vector<int> &drum, vector<int> &tata)
    {
        drum.clear();
        tata.clear();
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;

        auto cmp = [&](int nod1, int nod2)
        { return drum[nod1] > drum[nod2]; };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

        // daca am adaugat o sursa imaginara si doresc sa pornesc din locuri multiple :
        // for (int i = 1; i <= nrNoduri; i++)
        //     pq.push(i);

        pq.push(sursa);
        while (!pq.empty())
        {
            int nod = pq.top();
            pq.pop();

            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] + vecin.cost < drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    pq.push(vecin.nod);
                    tata[vecin.nod] = nod;
                }
            }
        }
    }

    // intoarce false daca contine circuit negativ, true daca nu
    bool BellmanFord(int sursa, vector<int> &drum, vector<int> &tata, int &negativStart)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        for (int k = 1; k <= nrNoduri - 1; k++)
        {
            for (auto muchie : muchii)
            {
                if (drum[muchie.x] < infinity && drum[muchie.x] + muchie.cost < drum[muchie.y])
                {
                    drum[muchie.y] = drum[muchie.x] + muchie.cost;
                    tata[muchie.y] = muchie.x;
                }
            }
        }
        // a n a rulare a algoritmului pentru a detecta ciclul negativ
        for (auto muchie : muchii)
        {
            if (drum[muchie.x] < infinity && drum[muchie.x] + muchie.cost < drum[muchie.y])
            {
                drum[muchie.y] = drum[muchie.x] + muchie.cost;
                tata[muchie.y] = muchie.x;
                negativStart = muchie.y;
                return false;
            }
        }
        return true;
    }

    // BellmanFord cu queue -> mai rapid decat primul si da 100% pe toate cazurile pe infoarena
    bool BellmanFordQueue(int sursa, vector<int> &drum, vector<int> &tata, int &negativStart)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        vector<bool> inQueue(nrNoduri + 1, false);
        queue<int> q;
        q.push(sursa);
        inQueue[sursa] = true;
        vector<int> lungime(nrNoduri + 1, 0);
        while (!q.empty())
        {
            int nod = q.front();
            q.pop();
            inQueue[nod] = false;
            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] < infinity && drum[nod] + vecin.cost < drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    tata[vecin.nod] = nod;
                    if (inQueue[vecin.nod] == false)
                    {
                        q.push(vecin.nod);
                        inQueue[vecin.nod] = true;
                    }
                    lungime[vecin.nod] = lungime[nod] + 1;
                    if (lungime[vecin.nod] > nrNoduri - 1)
                    {
                        negativStart = vecin.nod;
                        return false;
                    }
                }
            }
        }
        return true;
    }

    void afisareDrum(int start, int end, vector<int> tata)
    {
        // cout << start << " " << end << endl;
        // for (int i = 1; i <= nrNoduri; i++)
        //     cout << tata[i] << " ";
        // cout << endl;
        vector<int> drum;
        if (start != end) // daca e circuit nu trebuie sa punem finalul de 2 ori
            drum.push_back(end);
        while (tata[end] != start)
        {
            end = tata[end];
            drum.push_back(end);
        }
        drum.push_back(start);
        for (int i = drum.size() - 1; i >= 0; i--)
            cout << drum[i] << " ";
    }

    void FloydWarshall(vector<vector<int>> &drumuri, vector<vector<int>> &predecesor)
    {
        drumuri.resize(nrNoduri + 1);
        predecesor.resize(nrNoduri + 1);
        for (int nod = 1; nod <= nrNoduri; nod++)
        {
            drumuri[nod].resize(nrNoduri + 1, infinity);
            predecesor[nod].resize(nrNoduri + 1, 0);
            for (auto vecin : lista_adiacenta[nod])
            {
                drumuri[nod][vecin.nod] = vecin.cost;
                predecesor[nod][vecin.nod] = nod;
            }
        }
        for (int k = 1; k <= nrNoduri; k++)
        {
            for (int i = 1; i <= nrNoduri; i++)
            {
                for (int j = 1; j <= nrNoduri; j++)
                {
                    if (drumuri[i][k] < infinity && drumuri[k][j] < infinity)
                    {
                        if (drumuri[i][j] > drumuri[i][k] + drumuri[k][j])
                        {
                            drumuri[i][j] = drumuri[i][k] + drumuri[k][j];
                            predecesor[i][j] = predecesor[k][j];
                        }
                    }
                }
            }
        }

        for (int i = 1; i <= nrNoduri; i++)
        {
            for (int j = 1; j <= nrNoduri; j++)
            {
                if (drumuri[i][j] == infinity)
                    drumuri[i][j] = 0;
                if (i == j)
                    drumuri[i][j] = 0;
            }
        }
    }

    void drumMat(int x, int y, vector<vector<int>> predecesor)
    {
        if (x != y)
            drumMat(x, predecesor[x][y], predecesor);
        cout << y << " ";
    }
};

int main()
{
    int n;
    in >> n;
    Graf graf(n);
    // for (int i = 1; i <= graf.nrMuchii; i++)
    // {
    //     int x, y, c;
    //     in >> x >> y >> c;
    //     graf.muchii.push_back(Muchie(x, y, c));
    //     graf.lista_adiacenta[x].push_back(Nod(y, c));
    // }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int cost;
            in >> cost;
            if (cost != 0)
            {
                graf.muchii.push_back(Muchie(i, j, cost));
                graf.lista_adiacenta[i].push_back(Nod(j, cost));
            }
        }
    }
    // graf.printGraf();
    vector<vector<int>> drumuri;
    vector<vector<int>> predecesor;
    graf.FloydWarshall(drumuri, predecesor);
    // graf.printGraf();
    for (int i = 1; i <= graf.nrNoduri; i++)
    {
        for (int j = 1; j <= graf.nrNoduri; j++)
            out << drumuri[i][j] << " ";
        out << endl;
    }
    // cout << endl;

    // for (int i = 1; i <= graf.nrNoduri; i++)
    // {
    //     for (int j = 1; j <= graf.nrNoduri; j++)
    //         cout << predecesor[i][j] << " ";
    //     cout << endl;
    // }
    return 0;
}