#include <bits/stdc++.h>
using namespace std;
int top2();
int main() {
  int n;
  cin >> n;
  vector<vector<int> > a(n, vector<int>(n));
  int i = 0, j = 0, k = 0;
p1 : {
  j = 0;
p2 : {
  cin >> a[i][j];
  j++;
  if (j < n) goto p2;
}
  i++;
  if (i < n) goto p1;
}
  k = 0;
p3 : {
  i = 0;
p4 : {
  j = 0;
p5 : {
  a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
  j++;
  if (j < n) goto p5;
}
  i++;
  if (i < n) goto p4;
}
  k++;
  if (k < n) goto p3;
}
  int res = a[0][1];
  i = 0;
p6 : {
  j = 0;
p7 : {
  if (i != j) {
    res = max(res, a[i][j]);
  }
  j++;
  if (j < n) goto p7;
}
  i++;
  if (i < n) goto p6;
}
  cout << res << endl;
}
