#include <bits/stdc++.h>
int d[10][10];
int N;
int max = 0;
int read_in(int i, int j) {
  return (i == N) ? (0) : ((j == N) ? (read_in(i + 1, 0)) : ({
    scanf("%d", &(d[i][j]));
    read_in(i, j + 1);
  }));
}
int find_dist(int i, int j, int k) {
  return (k == N) ? (0)
                  : ((i == N) ? (find_dist(0, 0, k + 1))
                              : ((j == N) ? (find_dist(i + 1, 0, k)) : ({
                                  (d[i][j] > d[i][k] + d[k][j])
                                      ? (d[i][j] = d[i][k] + d[k][j])
                                      : (0);
                                  find_dist(i, j + 1, k);
                                })));
}
int find_max(int i, int j) {
  return (i == N) ? (0) : ((j == N) ? (find_max(i + 1, 0)) : ({
    (d[i][j] > max) ? (max = d[i][j]) : (0);
    find_max(i, j + 1);
  }));
}
int main() {
  scanf("%d", &N);
  read_in(0, 0);
  find_dist(0, 0, 0);
  find_max(0, 0);
  printf("%d\n", max);
}
