#include <bits/stdc++.h>
#define INF 1000001
using namespace std;
int N, tmp;
//각 도시간 이동하는데 드는 비용
int costs[10][10];
//인자 : 방문여부, 현재까지 든 비용, 이전 위치(도시), 이동한 도시 수, 시작한 도시
int shortest(vector<bool>& visited, int cost, int prev, int size, int first) {
if(size == N) return min(INF, cost+costs[prev][first]);
int ret = INF;
for(int i = 0; i < N; i++) {
if(visited[i]) continue;
visited[i] = true;
ret = min(shortest(visited, cost+costs[prev][i], i, size+1, first), ret);
visited[i] = false;
}
return ret;
}
int main() {
int cmp = INF;
cin.sync_with_stdio(false);
cin >> N;
vector<bool> visited(N, false);
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cin >> tmp;
if(tmp == 0){
costs[i][j] = INF;
}
else {
costs[i][j] = tmp;
}
}
}
//시작 도시 정하기
for (int i = 0; i < N; i++) {
visited[i] = true;
cmp = min(cmp, shortest(visited, 0, i, 1, i));
visited[i] = false;
}
cout << cmp;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgSU5GIDEwMDAwMDEKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IE4sIHRtcDsKLy/qsIEg64+E7Iuc6rCEIOydtOuPme2VmOuKlOuNsCDrk5zripQg67mE7JqpCmludCBjb3N0c1sxMF1bMTBdOwoKLy/snbjsnpAgOiDrsKnrrLjsl6zrtoAsIO2YhOyerOq5jOyngCDrk6Ag67mE7JqpLCDsnbTsoIQg7JyE7LmYKOuPhOyLnCksIOydtOuPme2VnCDrj4Tsi5wg7IiYLCDsi5zsnpHtlZwg64+E7IucCmludCBzaG9ydGVzdCh2ZWN0b3I8Ym9vbD4mIHZpc2l0ZWQsIGludCBjb3N0LCBpbnQgcHJldiwgaW50IHNpemUsIGludCBmaXJzdCkgeyAKCWlmKHNpemUgPT0gTikgcmV0dXJuIG1pbihJTkYsIGNvc3QrY29zdHNbcHJldl1bZmlyc3RdKTsKCWludCByZXQgPSBJTkY7Cglmb3IoaW50IGkgPSAwOyBpIDwgTjsgaSsrKSB7CgkJaWYodmlzaXRlZFtpXSkgY29udGludWU7CgkJdmlzaXRlZFtpXSA9IHRydWU7CgkJcmV0ID0gbWluKHNob3J0ZXN0KHZpc2l0ZWQsIGNvc3QrY29zdHNbcHJldl1baV0sIGksIHNpemUrMSwgZmlyc3QpLCByZXQpOwoJCXZpc2l0ZWRbaV0gPSBmYWxzZTsKCX0KCXJldHVybiByZXQ7Cn0KCmludCBtYWluKCkgewoJaW50IGNtcCA9IElORjsKCWNpbi5zeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwoJY2luID4+IE47Cgl2ZWN0b3I8Ym9vbD4gdmlzaXRlZChOLCBmYWxzZSk7Cglmb3IoaW50IGkgPSAwOyBpIDwgTjsgaSsrKSB7CgkJZm9yKGludCBqID0gMDsgaiA8IE47IGorKykgewoJCQljaW4gPj4gdG1wOwoJCQlpZih0bXAgPT0gMCl7CgkJCQljb3N0c1tpXVtqXSA9IElORjsKCQkJfQoJCQllbHNlIHsKCQkJCWNvc3RzW2ldW2pdID0gdG1wOwoJCQl9CgkJfQoJfQogICAgLy/si5zsnpEg64+E7IucIOygle2VmOq4sAoJZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspIHsKCQl2aXNpdGVkW2ldID0gdHJ1ZTsKCQljbXAgPSBtaW4oY21wLCBzaG9ydGVzdCh2aXNpdGVkLCAwLCBpLCAxLCBpKSk7CgkJdmlzaXRlZFtpXSA9IGZhbHNlOwoJfQoJY291dCA8PCBjbXA7Cn0=