фцв

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

signed main() {
    cout.precision(30);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n;
    vector<vector<ll>> gr(n, vector<ll>(n));
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            cin >> gr[i][j];
        }
    }
    ll dp[1 << n][n];
    for (ll mask = 0; mask < (1 << n); mask++) {
        for (ll i = 0; i < n; i++) {
            dp[mask][i] = INF;
        }
    }
    dp[1][0] = 0;
    vector<vector<pair<ll, ll>>> from(1 << n, vector<pair<ll, ll>>(n, {-1, -1}));
    for (ll mask = 1; mask < (1 << n); mask++) {
        for (ll i = 0; i < n; i++) {
            if (!((mask >> i) & 1)) continue;
            for (ll j = 0; j < n; j++) {
                if (!gr[i][j] || ((mask >> j) & 1)) continue;
                if (dp[mask | (1 << j)][j] > dp[mask][i] + gr[i][j]) {
                    dp[mask | (1 << j)][j] = dp[mask][i] + gr[i][j];
                    from[mask | (1 << j)][j] = {mask, i};
                }
            }
        }
    }
    ll mn = INF;
    pair<ll, ll> last;
    for (ll i = 0; i < n; i++) {
        if (mn > dp[(1 << n) - 1][i]) {
            mn = dp[(1 << n) - 1][i];
            last = {(1 << n) - 1, i};
        }
    }
    vector<ll> ans(n);
    if (mn == INF) {
        cout << -1;
        return 0;
    } else {
        ll cnt = 0, sm = 0;
        while (last.first != -1) {
            if (from[last.first][last.second].first != -1) {
                sm += gr[last.second][from[last.first][last.second].second];
            }
            ans[cnt++] = last.second;
            last = from[last.first][last.second];
        }
        cout << sm << '\n';
        std::reverse(ans.begin(), ans.end());
        for (ll i : ans) {
            cout << i + 1 << ' ';
        }
    }
}