#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;
}