---

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <climits>

using namespace std;

using us = unsigned int;
using matrix_type = vector<vector<long long>>;

const long long INF = 1e12;

void floyd(matrix_type& adjacency_matrix)
{
    us n = adjacency_matrix.size();
    
    for (us k = 0; k < n; ++k)
    {
        for (us i = 0; i < n; ++i)
        {
            for (us j = 0; j < n; ++j)
            {
                if (adjacency_matrix[i][k] < INF && adjacency_matrix[k][j] < INF)
                {
                    if (adjacency_matrix[i][j] > adjacency_matrix[i][k] + adjacency_matrix[k][j])
                    {
                        adjacency_matrix[i][j] = adjacency_matrix[i][k] + adjacency_matrix[k][j];
                    }
                }
            }
        }
    }
}

void read_matrix(matrix_type& adjacency_matrix)
{
    us n = adjacency_matrix.size();
    for (us i = 0; i < n; ++i)
    {
        for (us j = 0; j < n; ++j)
        {
            int val;
            cin >> val;
            
            if (i == j)
            {
                adjacency_matrix[i][j] = 0;
            }
            else if (val == -1)
            {
                adjacency_matrix[i][j] = INF;
            }
            else
            {
                adjacency_matrix[i][j] = val;
            }
        }
    }
}

int main()
{
    ifstream input("INPUT.TXT");
    ofstream output("OUTPUT.TXT");
    
    us N;
    input >> N;
    
    matrix_type adjacency_matrix(N, vector<long long>(N));
    
    for (us i = 0; i < N; ++i)
    {
        for (us j = 0; j < N; ++j)
        {
            int val;
            input >> val;
            
            if (i == j)
            {
                adjacency_matrix[i][j] = 0;
            }
            else if (val == -1)
            {
                adjacency_matrix[i][j] = INF;
            }
            else
            {
                adjacency_matrix[i][j] = val;
            }
        }
    }
    
    floyd(adjacency_matrix);
    
    long long max_distance = 0;
    for (us i = 0; i < N; ++i)
    {
        for (us j = 0; j < N; ++j)
        {
            if (i != j && adjacency_matrix[i][j] < INF)
            {
                if (adjacency_matrix[i][j] > max_distance)
                {
                    max_distance = adjacency_matrix[i][j];
                }
            }
        }
    }
    
    output << max_distance << endl;
    
    return 0;
}