#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>

using std::vector;

const int INF = 1 << 30;

int main() {
  int n;
  scanf("%d", &n);
  vector<vector<int> > a(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int x;
      scanf("%d", &x);
      a[i][j] = x;
    }
  }
  vector<vector<int> > dp(1 << n, vector<int> (n, INF));
  for (int mask = 1; mask < 1 << n; mask++) { // calculating DP
    if ((mask & (mask - 1)) == 0) {
      for (int i = 0; i < n; i++) if (((mask >> i) & 1) == 1) {
        dp[mask][i] = 0;
      }
      continue;
    }
    for (int last = 0; last < n; last++) {
      if (((mask >> last) & 1) == 0) continue;
      for (int prev = 0; prev < n; prev++) {
        int val = dp[mask ^ (1 << last)][prev];
        if (last == prev || ((mask >> prev) & 1) == 0 || val == INF) continue;
        dp[mask][last] = std::min(dp[mask][last], val + a[prev][last]);
      }
    }
  }
  int ans = INF;
  int last = -1;
  for (int i = 0; i < n; i++) { // finding best ''last'' vertex
    if (ans > dp[(1 << n) - 1][i]) {
      ans = dp[(1 << n) - 1][i];
      last = i;
    }
  }
  vector<int> path(n);
  int ac = n;
  for (int mask = (1 << n) - 1; ; ) { // restoring the answer using DP values
    path[--ac] = last;
    int cur = dp[mask][last];
    mask ^= 1 << last;
    if (mask == 0) break;
    int newLast = -1;
    for (int prev = 0; prev < n; prev++) {
      if (((mask >> prev) & 1) == 1 && cur == dp[mask][prev] + a[prev][last]) {
        newLast = prev;
        break;
      }
    }
    assert(newLast >= 0);
    last = newLast;
  }
  printf("%d\n", ans);
  for (int i = 0; i < n; i++) {
    if (i > 0) putchar(' ');
    printf("%d", path[i] + 1);
  }
  puts("");
}