#include <bits/stdc++.h>
using namespace std;
int n, a[10][10];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  vector<int> vec(n, 0);
  vector<int> noop;
  int i = 0;
  transform(vec.begin(), vec.end(), back_inserter(noop), [&](int x) {
    int j = 0;
    transform(vec.begin(), vec.end(), back_inserter(noop), [&](int y) {
      cin >> a[i][j];
      j += 1;
      return false;
    });
    i += 1;
    return false;
  });
  int k = 0;
  transform(vec.begin(), vec.end(), back_inserter(noop), [&](int x) {
    int i = 0;
    transform(vec.begin(), vec.end(), back_inserter(noop), [&](int y) {
      int j = 0;
      transform(vec.begin(), vec.end(), back_inserter(noop), [&](int z) {
        a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
        j += 1;
        return false;
      });
      i += 1;
      return false;
    });
    k += 1;
    return false;
  });
  int answer = 0;
  i = 0;
  transform(vec.begin(), vec.end(), back_inserter(noop), [&](int x) {
    int j = 0;
    transform(vec.begin(), vec.end(), back_inserter(noop), [&](int y) {
      answer = max(answer, a[i][j]);
      j += 1;
      return false;
    });
    i += 1;
    return false;
  });
  cout << answer << endl;
}
