#include <iostream>

using namespace std;
int n,dist[1005][1005];// matrice de distante
int main() {
        for (int i = 1;i<=n;++i) {
                for (int j = 1;j<=n;++j) {
                        cin>>dist[i][j];
                        // dist[i][j] = inf daca nu exista muchie
                        // dist[i][j] = 0 daca i == j
                        // dist[i][j] != 0 exista muchie intre i si j
                }
        }
        // ordinea e k i j,este important
        for (int k = 1;k<=n;++k) {
                for (int i = 1;i<=n;++i) {
                        for (int j = 1;j<=n;++j) {
                                // incercam sa actualizam dist de la i la j trecand prin nodul k
                                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
                        }
                }
        }
        return 0;
}