#include <bits/stdc++.h>
using namespace std;
int n, a[11][11], ans = 0, k;
int fk(int);
int fi(int, int);
int fj(int, int, int);
int read(int x, int y) {
  scanf("%d", &a[x][y]);
  return (x == n && y == n)
             ? 0
             : ((x < n && y == n) ? read(x + 1, 1) : read(x, y + 1));
}
int fk(int k) { return k == n + 1 ? 0 : (fi(1, k), fk(k + 1)); }
int fi(int i, int k) { return i == n + 1 ? 0 : (fj(1, i, k), fi(i + 1, k)); }
int fj(int j, int i, int k) {
  a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
  ans = (k == n) ? max(ans, a[i][j]) : ans;
  return j == n ? 0 : fj(j + 1, i, k);
}
int main() {
  scanf("%d", &n);
  read(1, 1);
  fk(1);
  printf("%d", ans);
  return 0;
}
