#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    ll n;
    cin >> n;
    ll g[20][20];
    vector <vector <ll>> dp(1ll << n, vector<ll>(n, 1000000000)), last(1ll << n, vector<ll>(n, 0));
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }
    dp[1][0] = 0;
    for (ll s = 0; s < (1ll << n); s++) {
        for (ll i = 0; i < n; i++) {
            if (!((s >> i) & 1ll))
                continue;
            for (ll j = 0; j < n; j++) {
                if (j == i || !((s >> j) & 1ll))
                    continue;
                if (dp[s][i] > dp[s ^ (1ll << i)][j] + g[j][i])
                    last[s][i] = j;
                dp[s][i] = min(dp[s][i], dp[s ^ (1ll << i)][j] + g[j][i]);
            }
        }
    }
    ll w = dp[(1ll << n) - 1][0], ans1 = 0;
    for (ll i = 1; i < n; i++) {
        if (w > dp[(1ll << n) - 1][i])
            ans1 = i;
        w = min(w, dp[(1ll << n) - 1][i]);
    }
    cout << w << '\n';
    for (ll i = 0; i < n; i++) {
        cout << ans1 + 1 << ' ';
        ans1 = last[(1 << n) - 1][ans1];
    }
    return 0;
}