#include <iostream>
#include <vector>
using namespace std;
const int inf = -(1e+9);
int n, k;
int mas[13][13];
int d[13][13];
int dp[13 * 13][3][13];
int main() {
	/*freopen("ladder.in", "r" ,stdin);
	freopen("ladder.out", "w", stdout);*/
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> mas[i][j];
			d[i][j] = mas[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			for (int k = 0; k < n; k++) {
				d[i][j] = max(d[i][j], d[i][j] + d[i][k] + d[k][j]);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dp[i * 13 + j][0][2] = i;
			dp[i * 13 + j][1][2] = j;
			dp[i * 13 + j][2][2] = -1;
		}
	}
	for (int i = 3; i <= n; i++) {
		int c = 0;
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 169; k++) {
				if (d[j][dp[k][0][i - 1]] != 0 && (dp[k][0][i - 1] + dp[k][1][i - 1])) {
					dp[c][0][i] = j;
					dp[c][2][i] = k;
					c++;
				}
				if (d[dp[k][0][i - 1]][j] != 0) {
					dp[c][1][i] = j;
					dp[c][2][i] = k;
					c++;
				}
			}
		}
	}
	for (int k = 0; k < 169; k++) {
		for (int i = n; i >= 3; i++) {

		}
	}
	return 0;