/*
 * Supr*
 * Fie un graf citit dintr-un fisier
 * a) sa se determine nodurile izolate din grad
 * b) sa se dteremine daca graful este regular
 * c) avand matricea de adiacenta sa se det matricea distantelor
 * d) sa se determine daca graful este conex
 */
#include <fstream>
#include <vector>
#include <climits>
#include <deque>
#define pb push_back
#define MAX_N 101
using namespace std;

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

vector <int>G[MAX_N];
deque <int> Q;
bool viz[MAX_N], conex, regular;
int adj[MAX_N][MAX_N];
int n = 0, m = 0;
int dist[MAX_N][MAX_N];
int infinity = INT_MAX;

void read_data(int &n, int &m, vector <int>G[MAX_N], int adj[MAX_N][MAX_N]) {
    f >> n;
    m = 0;
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=n; j++) {
            f >> adj[i][j];
        }
    }
    for(int i =1; i<=n; i++) {
        for(int j = 1; j<=i; j++) {
            if(adj[i][j] != 0) {
                G[i].pb(j);
                G[j].pb(i);
            }
        }
    }
}

void print_isolated(vector <int> G[MAX_N]) {
    bool has_isolated = false;
    for(int i = 1; i<=n; i++) {
        if(G[i].size() == 0) {
            g << "Nodul " << i << " este izolat\n";
            has_isolated = true;
        }
    }
    if(has_isolated == false) {
        g<<"Graful nu are noduri izolate!";
    }
     g << "\n";
}

bool is_regular(vector<int> G[MAX_N]) {
    int num = G[0].size();
    for(int i = 2; i<=n; i++) {
        if(G[i].size() != num) {
            return false;
        }
    }
    return true;
}

bool is_conex(int start, vector <int>G[MAX_N], deque <int> Q, bool viz[MAX_N]) {
    Q.pb(start);
    viz[start] = true;

    while(!Q.empty()) {
        int node = Q.front();
        Q.pop_front();
        for(unsigned i = 0; i<G[node].size(); i++) {
            if(viz[G[node][i]] == false) {
                viz[G[node][i]] = true;
                Q.push_back(G[node][i]);

            }
        }
    }
    for(int i = 1; i<=n; i++) {
        if(viz[i] == false) {
            return false;
        }
    }
    return true;
}

bool check_inf(int number) {
    return number == infinity;
}

void roy_floyd(int adj[MAX_N][MAX_N], int dist[MAX_N][MAX_N]) {
    for(int i = 1; i<=n; i++) {
        dist[i][i] = 0;
        for(int j = 1; j<=n; j++) {
            if(i != j) {
                dist[i][j] = infinity;
            }
        }
    }
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=n; j++) {
            if(adj[i][j]) {
                dist[i][j] = adj[i][j];
            }
        }
    }

    for(int k = 1; k<=n; k++) {
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=n; j++) {
                if(dist[i][j] > dist[i][k] + dist[k][j] && !check_inf(dist[i][k]) && !check_inf(dist[k][j])) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=n; j++) {
            if(dist[i][j] != infinity) {
                g << dist[i][j] << ' ';
            }
            else g << 0 << ' ';
        }
        g << "\n";
    }
    g << "\n";
}

int main(){
    read_data(n, m, G, adj);
    /*
    print_isolated(G);
    regular = is_regular(G);
    if(regular == false) {
        g << "Graful nu este regular!\n";
    }
    else {
        g << "Graful este regular!\n";
    }
    conex = is_conex(1, G, Q, viz);
    roy_floyd(adj, dist);
    if(conex == false) {
        g << "Graful nu este conex!";
    }
    else {
        g << "Graful este conex!";
    }*/
    roy_floyd(adj, dist);
    return 0;
}