// Fie un graf orientat G=(V,E) dat prin matricea de pondere. Sa se determine pentru
// oricare doua pereche de noduri x,y drumul de cost minim
// Complexitate dorita: O(|V|^3);
// Ideea: Se va folosi algoritmul Floyd-Warshall/Roy-Floyd. 
// Explicatie pe scurt: Fie d^(i)[x][y] drumul de cost minim de la x la y folosind
// maxim i muchii intermediare. Atunci
// d^(0)[x][y] = cost[x][y];
// d^(k)[x][y] = min( d^(k-1)[x][i] + cost[i][y]);
// Se observa foarte usor ca pentru k>n: d^(k)[x][y] = d^(n)[x][y];

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


const char InFile[] = "royfloyd.in";
const char OutFile[] = "royfloyd.out";

class RoyFloyd{
    int** matrix;
    int V;

    public:
        RoyFloyd(int V) : V(V) {
            matrix = new int*[V] ;
            for( int i=0 ; i<V ; i++ )
                matrix[i] = new int[V];
        }

//        virtual ~RoyFloyd() {
//            for( int i=0 ; i<V ; i++ )
//                delete[] matrix[i];
//            delete[] matrix;
//        }

        void addCost(int i, int j, int value){
            matrix[i][j] = value;
        }

        void solve(){
            int i,j,k;

            for( k=0 ; k<V ; k++ )
                for( i=0 ; i<V ; i++ )
                    for( j=0 ; j<V ; j++ )
                        if( i != j && matrix[i][k] != 0 && matrix[k][j] != 0 &&
                                ( matrix[i][j] == 0 || matrix[i][j] > matrix[i][k] + matrix[k][j] ) )
                            matrix[i][j] = matrix[i][k] + matrix[k][j];
        }

        friend std::ostream& operator<< (std::ostream& out, RoyFloyd graph);
};

std::ostream& operator<< (std::ostream& out, RoyFloyd graph){
    int i,j;
    for( i=0 ; i<graph.V ; i++ ){
        for( j=0 ; j<graph.V-1 ; j++ )
            out << graph.matrix[i][j] << ' ';
        out << graph.matrix[i][j] << '\n';
    }
    return out;
}

RoyFloyd readData(std::istream& in)
{
    int V;

    in >> V;
    RoyFloyd graph(V);

    int i,j,x;
    for( i=0 ; i<V ; i++ )
        for( j=0 ; j<V ; j++ ){
            in >> x;
            graph.addCost(i, j, x);
        }
    return graph;
}

int main(void)
{
    std::ifstream in(InFile);
    std::ofstream out(OutFile);

    RoyFloyd graph = readData(in);

    graph.solve();
    out << graph;

    return 0;
}