#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using ld = long double;
using pii = pair<int, int>;
template <class F>
void bleh(int i, int n, F f) {
  f(i);
  poop(i + 1, n, f);
}
template <class F>
void poop(int i, int n, F f) {
  return (i == n) ? void() : bleh(i, n, f);
}
int main() {
  int n;
  cin >> n;
  int oo = (int)1e9;
  vector<vector<int>> d(n, vector<int>(n, oo));
  poop(0, n, [&](int i) { d[i][i] = 0; });
  poop(0, n, [&](int i) { poop(0, n, [&](int j) { cin >> d[i][j]; }); });
  poop(0, n, [&](int k) {
    poop(0, n, [&](int i) {
      poop(0, n, [&](int j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); });
    });
  });
  int ans = 0;
  poop(0, n, [&](int i) {
    poop(0, n, [&](int j) { ans = (d[i][j] < oo) ? max(ans, d[i][j]) : ans; });
  });
  cout << ans << '\n';
  return 0;
}
