#include <iostream>
using namespace std;

int MAX_INT = 2147483647;
int dist[21][21];
int otvet[10000000][21];
int n_planet[10000000][21];

int rec(int mask, int pos, int n) {
    if (otvet[mask][pos] != 0)
        return otvet[mask][pos];
    if (mask == (1 << n) - 1)
        return 0;
    int ans = MAX_INT;
    for (int i = 0; i < n; i++) {
        if (!((1 << i) & mask)) {
            int x = rec(mask | (1 << i), i, n) + dist[pos][i];
            ans = min(x, ans);
            if (x == ans)
                n_planet[mask][pos] = i;
        }
    }
    otvet[mask][pos] = ans;
    return otvet[mask][pos];
}


int main() {
    int n;
    cin >> n;
    int k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> k;
            dist[i][j] = k;
            if (i == j)
                dist[i][j] = 0;
        }
    }

    int ans = MAX_INT;
    int planet;
    for (int i = 0; i < n; i++) {
        int tmp = rec(1 << i, i, n);
        ans = min(tmp, ans);
        if (tmp == ans)
            planet = i;
    }

    cout << ans << "\n";
    cout << planet + 1<< " ";
    int new_mask = 1 << planet;
    for (int i = 0; i < n - 1; i++) {
        cout << n_planet[new_mask][planet] + 1 << " ";
        planet = n_planet[new_mask][planet];
        new_mask = new_mask | (1 << planet);
    }
    return 0;
}