#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:16777216")
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979

typedef long long LL;
typedef vector <int> VI;
typedef pair <int, int> PII;
using namespace std;


const int MAX = 444;

int n;
int D[MAX][MAX];

int NXT[MAX], PR[MAX];
int COL[MAX];

vector<int> solve1()
{
	FOR(i, 0, n)
	{
		NXT[i] = -1;
		PR[i] = -1;
		COL[i] = i;
	}

	FOR(it, 0, n)
	{
		int s = -1, t = -1;
		int dmin = 1e+9;
		FOR(i, 0, n)
			if (NXT[i] == -1)
			{
				FOR(j, 0, n)
					if (PR[j] == -1 && (COL[i] != COL[j] || it == n - 1))
					{
						if (D[i][j] < dmin)
						{
							dmin = D[i][j];
							s = i;
							t = j;
						}
					}
			}

		NXT[s] = t;
		PR[t] = s;
		int c = COL[t];
		FOR(i, 0, n)
		{
			if (COL[i] == c)
				COL[i] = COL[s];
		}
	}

	int v = 0;

	vector<int> res;

	FOR(i, 0, n + 1)
	{
		res.push_back(v);
		v = NXT[v];
	}

	return res;
}

const int MAXDP = 20;
int DP[MAXDP][1 << MAXDP];

LL getDp(int v, int mask) {
	if (DP[v][mask] != -1)return DP[v][mask];
	int val = 1e+9;
	int p = -1;
	FOR(i, 0, n)
	{
		if (i == v)continue;
		if (!(mask&(1 << v)))continue;
		int cur = getDp(i, mask ^ (1 << v)) + D[i][v];
		if (cur < val) {
			val = cur;
			p = i;
		}
	}

	DP[v][mask] = val;
	return val;
}

vector<int> solveDP()
{
	FILL(DP, -1);
	DP[0][0] = 0;
	getDp(0, (1 << n) - 1);
	//cerr << "done" << endl;
	vector<int> res;
	int v = 0;
	int msk = (1 << n) - 1;

	while (msk)
	{
		res.PB(v);
		int to = -1;
		FOR(i,0,n)
		  if(i!=v)
			if(msk&(1<<i))
				if (DP[i][msk ^ (1 << v)] + D[i][v] == DP[v][msk]) {
					to = i;
				}
		msk ^= 1 << v;
		v = to;
	}
	res.PB(0);

	return res;
}

struct BranchSolver {
	bool us[MAX];
	VI bstPath;
	VI path;
	LL cost;
	LL LB;
	vector<PII> E[MAX];
	void init(LL lb)
	{
		LB = lb;
		FILL(us, 0);
		FOR(i, 0, n)
		{
			FOR(j, 0, n)if (i != j)E[i].PB(MP(D[i][j], j));
			sort(ALL(E[i]));
		}
	}

	PII getMin(int v) {
		FOR(i, 0, SZ(E[v]))
			if (!(us[E[v][i].second] /*&&rand()%7==0*/))return E[v][i];
		return MP(0,-1);
	}

	LL getEstim()
	{
/*		LL res = 0;
		FOR(i,0,n)
			if (!us[i]) {
				PII w = getMin(i);
				res += w.first;
			}*/
		LL avgEdge = LB / (n) * (n - path.size());
		return avgEdge;
	}
	bool END = false;
	void go(int v)
	{
		if (END || (path.size()&8) && (clock() / (double)CLOCKS_PER_SEC) > 0.21) {
			END = true; return;
//			cerr << "end";	exit(0);
		}
		if (path.size() == n) {
			if (cost+D[v][0] < LB) {
				LB = cost+D[v][0];
				bstPath = path;
			}
			return;
		}
		if (cost + getEstim() >= LB) return;

		FOR(ind, 0, n-1) {
			int i = E[v][ind].second;
			if (us[i])continue;
			us[i] = 1;
			path.push_back(i);
			cost += D[v][i];
			go(i);
			cost -= D[v][i];
			us[i] = 0;
			path.pop_back();
			 if ((v&47))break;
		}
	}

	VI solve() {
		us[0] = 1;
		END = 0;
		cost = 0;
		path.PB(0);
		go(0);
		bstPath.PB(0);
		return bstPath;
	}

} BRANCH;


LL getScore(vector<int> &v)
{
	LL res = 0;
	FOR(i, 1, SZ(v))
		res += D[v[i - 1]][v[i]];

	return res;
}

void optimize(vector<int>& v)
{
	LL score = getScore(v);
	FOR(i, 2, v.size() - 1)
	{
		int before = D[v[i-2]][v[i-1]] + D[v[i]][v[i+1]];
		int after = D[v[i-2]][v[i]] + D[v[i-1]][v[i+1]];

		if (after < before)
		{
			swap(v[i], v[i-1]);
		}
//		swap(v[i], v[i - 1]);
//		LL cur = getScore(v);
//		if (cur > score)
//		{
//			swap(v[i], v[i - 1]);
//		}
//		score = min(score, cur);
	}
}

void optimize2(VI& v)
{
	int x = rand() % (SZ(v) - 1);
	int y = rand() % (SZ(v) - 1);

	if (x == y) return;
	if (x > y) swap(x, y);

	int before = D[v[x]][v[x+1]] + D[v[y]][v[y+1]];
	int after = D[v[x]][v[y]] + D[v[x+1]][v[y+1]];
	if (after < before)
	{
		reverse(v.begin() + x + 1, v.begin() + y + 1);
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);

	cin >> n;
	FOR(i, 0, n)
		FOR(j, 0, n)
	{
//		D[i][j] = 1;
		cin >> D[i][j];
	}

	vector<int> v;

	if (n < MAXDP) {
		v = solveDP();
	}
	else
	{
		v = solve1();

		BRANCH.init(getScore(v));
		VI vBr = BRANCH.solve();
		if (vBr.size()==n+1 && getScore(vBr) < getScore(v))v = vBr;
		FOR(it, 0, 6000)
		{
			FOR (it, 0, 1000)
			{
				optimize2(v);
			}
			optimize(v);
		}
	}
	cout << getScore(v) << "\n";
	FOR(i, 0, SZ(v))cout << v[i] + 1 << " ";

	//  getchar();
	// getchar();
}