#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include "optimization.h"
#include <unordered_map>

#define all(a) a.begin, a.end()
using namespace std;

int main() {
    int64_t n;
    cin >> n;
    vector<vector<int64_t>> cost(n, vector<int64_t>(n));
    for (int64_t i = 0; i < n; i++) {
        for (int64_t j = 0; j < n; j++) {
            cin >> cost[i][j];
        }
    }
    vector<vector<int64_t>> dp((1 << n), vector<int64_t>(n, INT32_MAX));
    vector<vector<int64_t>> last((1 << n), vector<int64_t>(n, INT16_MAX));
    for (int64_t i = 0; i < n; i++) {
        dp[1 << i][i] = 0;
    }
    for (int64_t A = 1; A < (1 << n); A++) {
        for (int64_t v = 0; v < n; v++) {
            for (int64_t x = 0; x < n; x++) {
                if ((A & (1 << x)) == 0 && dp[A][v] != INT32_MAX && dp[A][v] + cost[v][x] < dp[A | (1 << x)][x]) {
                    dp[A | (1 << x)][x] = dp[A][v] + cost[v][x];
                    last[A | (1 << x)][x] = v;
                }
            }
        }
    }
    int64_t cur = INT32_MAX;
    int64_t res = INT32_MAX;
    for (int64_t v = 0; v < n; v++) {
        if (dp[(1 << n) - 1][v] < res) {
            res = dp[(1 << n) - 1][v];
            cur = v;
        }
    }
    cout << dp[(1 << n) - 1][cur] << "\n";

    vector<int64_t> way(n);
    int64_t j = n - 1;
    int64_t A = (1 << n) - 1;
    int pref = 0;
    way[j--] = cur + 1;
    while (j != -1){
        int pref = last[A][cur];
        A = A - (1 << cur);
        way[j--] = pref + 1;
        cur = pref;
    }
    for (auto x: way) {
        cout << x << " ";
    }
}