#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
int main(){
int n; cin >> n;
vector <vector<int>> graph(n, vector<int>(n)); //adjacency matrix with weights
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> graph[i][j];
}
}
vector <vector<int>> dp(n, vector<int>(1 << n, 2e9));
for (int i = 0; i < n; ++i) {
dp[i][(1 << n)-1] = graph[i][0];
}
//better way to apply masks? in O(1) space??
vector <int> all_masks(1 << n);
iota(all(all_masks), 0);
sort(all(all_masks), [&](int a, int b) {
return __builtin_popcount(a) < __builtin_popcount(b);
});
reverse(all(all_masks));
//here..
for (int m: all_masks) {
int x = __builtin_popcount(m);
for (int i = 0; i < n; ++i) {
if (!(m >> i & 1)) continue;
for (int j = 0; j < n; ++j) {
if (m >> j & 1) continue;
dp[i][m] = min(dp[i][m], graph[i][j] + dp[j][m | (1 << j)]);
}
}
}
cout << dp[0][1] << endl;
//finding path
vector <int> path{0};
int curr = 0;
int mask = 1;
while (mask != (1 << n)-1) {
int dist = 2e9, node = -1;
for (int i = 0; i < n; ++i) {
if (mask >> i & 1) continue;
if (dist > graph[curr][i] + dp[i][mask | (1 << i)]) {
dist = graph[curr][i] + dp[i][mask | (1 << i)];
node = i;
}
}
assert(node >= 0);
path.push_back(node);
mask |= (1 << node);
curr = node;
}
for (int i: path) cout << i << ' ';
return 0;
}