#include <bits/stdc++.h>
using namespace std;
const int N = (int)10;
int n;
int mat[N][N];
int FOR3(const int& k, const int& i, const int& j, const int& n) {
  mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
  return j + 1 < n ? FOR3(k, i, j + 1, n) : 0;
}
int FOR2(const int& i, const int& j, const int& n) {
  FOR3(i, j, 0, n);
  return j + 1 < n ? FOR2(i, j + 1, n) : 0;
}
int FOR1(const int& i, const int& n) {
  FOR2(i, 0, n);
  return i + 1 < n ? FOR1(i + 1, n) : 0;
}
int FOR_INPUT2(const int& i, const int& j, const int& n) {
  cin >> mat[i][j];
  return j + 1 < n ? FOR_INPUT2(i, j + 1, n) : 0;
}
int FOR_INPUT1(const int& i, const int& n) {
  FOR_INPUT2(i, 0, n);
  return i + 1 < n ? FOR_INPUT1(i + 1, n) : 0;
}
int BILLY2(const int& i, const int& j, const int& n) {
  int ans = mat[i][j];
  int other = j + 1 < n ? BILLY2(i, j + 1, n) : 0;
  return max(ans, other);
}
int BILLY1(const int& i, const int& n) {
  int ans = BILLY2(i, 0, n);
  int other = i + 1 < n ? BILLY1(i + 1, n) : 0;
  return max(ans, other);
}
void solve() {
  cin >> n;
  FOR_INPUT1(0, n);
  FOR1(0, n);
  cout << BILLY1(0, n) << endl;
}
int main() {
  solve();
  return 0;
}
