#include <bits/stdc++.h>
using namespace std;

ifstream fin("rf.in");
ofstream fout("rf.out");

const int INF = 1e9;
const int NMAX = 270;
struct DUO{int f1, f2;};
int n, adj[NMAX][NMAX], dp[NMAX][NMAX];
DUO strazi[NMAX][NMAX];

inline void rf()
{
    for(int k=0;k<=n;++k)
    {
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(!k)
                    dp[i][j] = adj[i][j];
                else
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
            fout << dp[i][j] << ' ';
        fout << '\n';
    }
}

inline void task2()
{
    for(int k=0;k<=n;++k)
    {
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(!k)
                    strazi[i][j].f1 = 0, strazi[i][j].f2 = adj[i][j];
                else
                {
                    if(strazi[i][j].f2 >= strazi[i][k].f2 + strazi[k][j].f2)
                    {
                        strazi[i][j].f1++;
                        strazi[i][j].f2 = strazi[i][k].f2 + strazi[k][j].f2;
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            fout << strazi[i][j].f1-1 << ' ';
        }
        fout << '\n';
    }
}

inline void solve()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(adj[i][j] == 0 && i!=j)
                adj[i][j] = INF;
        }
    }
    rf();
    task2();
}

int main()
{
    fin >> n;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            fin >> adj[i][j];
    solve();
}