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