#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int INF = (int) 1e8;

int dp[<<][]; //dp[S][v] 表示还需访问的集合为S, 现在在v点

int d[][];

int n;

void floyd() {

    for (int k = ; k <= n; k++) {

        for (int i = ; i <= n; i++)

            for (int j = ; j <= n; j++)

                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);

    }

}

void print() {

    for (int i = ; i <= n; i++) {

        for (int j = ; j <= n; j++)

            printf("%d ", d[i][j]);

        puts("");

    }

}

int main() {

    #ifdef Phantom01

        freopen("PKU3311.txt", "r", stdin);

    #endif // Phantom01

    while (scanf("%d", &n)!=EOF) {

        if (==n) break;

        for (int i = ; i <= n; i++)

            for (int j = ; j <= n; j++)

                scanf("%d", &d[i][j]);

//        print();

        floyd();

//        print();

        for (int i = ; i <= n; i++)

            for (int S = ; S < (<<(n+)); S++)

                dp[S][i] = INF;

        dp[(<<(n+))-][] = ;

        for (int S = (<<(n+))-; S >= ; S--) {

            for (int v = ; v <= n; v++) {

                for (int u = ; u <= n; u++) {

                    if (!(S&(<<u))) {

                        if (dp[S][v] < ) {

                            dp[S][v] = dp[S|(<<u)][u] + d[v][u];

                        } else {

                            dp[S][v] = min(dp[S][v], dp[S|(<<u)][u] + d[v][u]);

                        }

                    }

                }

            }

        }

        printf("%d\n", dp[][]);

    }

    return ;

}