О╩©#include <bits/stdc++.h>

using namespace std;

const int N = 100;

vector<vector<int>> g(N, vector<int>(N));

int main()
{
#ifdef AT_MY_PC
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
        {
            cin >> g[i][j];
            if(g[i][j] == -1)
                g[i][j] = 10000;
        }
    for (int k=0; k<n; ++k)
        for (int i=0; i<n; ++i)
            for (int j=0; j<n; ++j)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    int ans = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            if(g[i][j] < 10000)
                ans = max(ans, g[i][j]);
    cout << ans;

    return 0;
}