#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
long long i, j, n, s, ans;
long long A[15][15];
int scan() {
  scanf("%lld", A[i] + j);
  s++;
  j++;
  i += (j == n + 1 ? 1 : 0);
  j = (j == n + 1 ? 1 : j);
  return s == n * n ? 1 : scan();
}
int first(int x);
int second(int x, int y);
int third(int x, int y, int z);
int ssecond(int x, int y);
int third(int x, int y, int z) {
  A[y][z] = (z == n + 1 ? A[y][z] : min(A[y][z], A[y][x] + A[x][z]));
  return z == n + 1 ? second(x, y + 1) : third(x, y, z + 1);
}
int second(int x, int y) { return y == n + 1 ? first(x + 1) : third(x, y, 1); }
int first(int x) { return x == n + 1 ? 1 : second(x, 1); }
int sfirst(int x) { return x == n + 1 ? 1 : ssecond(x, 1); }
int ssecond(int x, int y) {
  ans = (y == n + 1 ? ans : max(ans, A[x][y]));
  return y == n + 1 ? sfirst(x + 1) : ssecond(x, y + 1);
}
int main() {
  scanf("%lld", &n);
  i = 1;
  j = 1;
  scan();
  first(1);
  sfirst(1);
  printf("%lld", ans);
}
