#include <iostream>
#define inf 9223372036854775807

using namespace std;
int n;
long long ans[19][1 << 19];
long long g[19][19];

int main() {
    cin >> n;
    long long i, j, a, k;
    for(k = 0; k < n; k++){
        for(int l = 0; l < n; l++){
            cin >> g[k][l];
        }
    }

    for (i = 0; i < n; i++) {
        ans[i][1 << i] = 0;
    }


    for (a = 1; a < (1 << n) - 1; a++) {
        for (j = 0; j < n; j++) {
            if ((a & (1 << j)) == 0) {
                ans[j][a | (1 << j)] = inf;
                for (k = 0; k < n; k++) {
                    if ((a & (1 << k)) != 0) {
                        if (ans[j][a | (1 << j)] > ans[k][a] + g[k][j]) {
                            ans[j][a | (1 << j)] = ans[k][a] + g[k][j];
                        }
                    }
                }
            }
        }
    }

    long long  minp = inf;
    int p, last = 0;
    for( p = 0; p < n; p++){
        if(ans[p][(1 << n) - 1] < minp){
            minp = ans[p][(1 << n) - 1];
            last = p;
        }
    }

    cout << minp << endl;
    i = last;
    j = ((1 << n) - 1);
    cout << last + 1 << " " << endl;
    for (j ^= (1 << i); j > 0; ) {
        for (k = 0; k < n; k++) {
            if ((j & (1 << k)) != 0) {
                if (ans[k][j] == ans[k][j ^ (1 << k)] + g[k][i]) {
                    cout << k + 1 << " ";
                    i = k;
                    j ^= (1 << k);
                    break;
                }
            }
        }
    }

    return 0;
}