#include <bits/stdc++.h>
int a[15][15];
int i, j, k, n, mx;
void r(void) {
  i < n ? j < n ? (scanf("%d", &a[i][j]), j++) : (i++, j = 0) : i = j = n;
}
void relax(void) {
  a[i][j] = (a[i][j] < a[i][k] + a[k][j] ? a[i][j] : a[i][k] + a[k][j]);
}
void relax2(void) { mx = (mx > a[i][j] ? mx : a[i][j]); }
void f(void) {
  k < n ? i < n ? j < n ? (relax(), j++) : (i++, j = 0) : (k++, i = 0, j = 0)
        : i = j = k = n;
}
void fmx(void) { i < n ? j < n ? (relax2(), j++) : (i++, j = 0) : i = j = n; }
void d1000(void);
int main(void) {
  scanf("%d", &n);
  memset(a, 0x3f, sizeof a);
  i = 0;
  j = 0;
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  r();
  ;
  i = 0;
  j = 0;
  k = 0;
  d1000();
  mx = 0;
  i = 0;
  j = 0;
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  fmx();
  printf("%d\n", mx);
  return 0;
}
void d1000(void) {
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  f();
  ;
}
