#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m, x, y, l;
    cin >> n;
    int d[n][n];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) {
            cin >> d[i][j];
            if(d[i][j] == -1)
                d[i][j] = 1000000;
        }

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    long long r = 1000000, dm = 0;
    for(int i = 0; i < n; i++){
        int temp = 0;
        for(int j = 0; j < n; j++)
            if(d[i][j] > temp)
                temp = d[i][j];
        if(temp > dm)
            dm = temp;
        if(temp < r)
            r = temp;
    }
    cout << dm << endl << r << endl;
    return 0;
}