#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > d;
int n;
bool read(int i, int j) {
  cin >> d[i][j];
  return j + 1 == n ? i + 1 == n ? false : read(i + 1, 0) : read(i, j + 1);
}
bool floyd(int k, int i, int j) {
  d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  return j + 1 == n ? i + 1 == n ? k + 1 == n ? false : floyd(k + 1, 0, 0)
                                 : floyd(k, i + 1, 0)
                    : floyd(k, i, j + 1);
}
int main() {
  cin >> n;
  d.resize(n, vector<int>(n));
  read(0, 0);
  floyd(0, 0, 0);
  int answer = 0;
  for_each(d.begin(), d.end(), [&](vector<int>& v) {
    answer = max(answer, *max_element(v.begin(), v.end()));
  });
  cout << answer;
  return 0;
}
