#include <bits/stdc++.h>
using namespace std;
int n, dis[20][20], maxn = 0;
int R(int a, int b) {
  return b < n ? (scanf("%d", &dis[a][b]), R(a, b + 1))
               : (a + 1 < n ? R(a + 1, 0) : 1);
}
int Floyd(int i, int j, int k) {
  return j < n ? (dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]),
                  Floyd(i, j + 1, k))
               : (i + 1 < n ? (Floyd(i + 1, 0, k))
                            : (k + 1 < n ? (Floyd(0, 0, k + 1)) : 1));
}
int M(int i, int j) {
  return j < n ? (maxn = max(maxn, dis[i][j]), M(i, j + 1))
               : (i + 1 < n ? (M(i + 1, 0)) : 1);
}
int main() {
  scanf("%d", &n);
  R(0, 0);
  Floyd(0, 0, 0);
  M(0, 0);
  printf("%d\n", maxn);
  return 0;
}
