#include <bits/stdc++.h>
using namespace std;
int n, mx, a[20][20];
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) cin >> a[i][j];
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j) a[i][j] = min(a[i][k] + a[k][j], a[i][j]);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) mx = max(a[i][j], mx);
  cout << mx;
}
