// Floyd–Warshall.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main()
{

	int n;

	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);

	cin >> n;

	vector<vector<int>> graph(n);

	for (int i = 0; i < n; i++){
		graph[i] = vector<int>(n);
		for (int j = 0; j < n; j++){
			cin >> graph[i][j];
		}
	}

	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (graph[i][k] != -1 && graph[k][j] != -1) {
					if (graph[i][j] != -1) {
						graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
					}
					else {
						graph[i][j] = graph[i][k] + graph[k][j];
					}
				}
			}
		}
	}
	int _max = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			_max = max(graph[i][j], _max);
		}
	}

	cout << _max;

    return 0;
}