#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <iterator>
#include <functional>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <list>
#include <sstream>
#include <cstring>
#include <stdio.h>
#include <bitset>
#include <complex>
#include <cassert>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

typedef double LD;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LD, LD> PDD;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<LD> VLD;
typedef vector<string> VS;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define prev fake_prev
#define left fake_left
#define right fake_right

#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 REP(i, t) FOR(i, 0, t)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))

const LD PI = acos(-1.0);
const LD EPS = 1e-7;
const LL INF = 1e9 + 47;
const LL LINF = 1e18;
const LL mod = 1e9 + 7;
const LL MAX = 400;

int n;
int d[MAX][MAX];
char used[MAX];

pair<int, VI> greedy()
{
	FILL(used, 0);
	used[0] = 1;
	int ans = 0;
	int curr = 0;
	VI res;
	res.push_back(0);

	while (1)
	{
		bool ok = 0;
		FOR(i, 0, n)
			if (used[i] == 0)
				ok = 1;

		if (!ok)
		{
			ans += d[curr][0];
			res.push_back(0);
			break;
		}

		int best = -1;
		FOR(i, 0, n)
		{
			if (used[i])
				continue;
			if (best == -1 || d[curr][best] > d[curr][i])
				best = i;
		}

		ans += d[curr][best];
		res.push_back(best);
		curr = best;
		used[best] = 1;
	}

	return MP(ans, res);
}

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

int solve(int mask, int now)
{
	if (DP[mask][now] != -1)
		return DP[mask][now];

	int res = INF;
	FOR(i, 0, n)
	{
		if (mask & (1 << i))
			continue;

		res = min(res, d[now][i] + solve(mask | (1 << i), i));
	}

	if (res == INF)
		res = d[now][0];

	return DP[mask][now] = res;
}

void brute()
{
	assert(n > 1);
	FILL(DP, -1);
	int best = -1, ans = INF;
	FOR(i, 1, n)
	{
		int r = solve(1 + (1 << i), i) + d[0][i];
		if (r < ans)
		{
			ans = r;
			best = i;
		}
	}

	cout << ans << endl;
	VI path;

	path.push_back(0);
	path.push_back(best);
	int curr = 1 + (1 << best);

	while (curr != (1 << n) - 1)
	{
		FOR(i, 0, n)
		{
			if (curr & (1 << i))
				continue;

			bool ok = 0;

			if (solve(curr | (1 << i), i) == solve(curr, best) - d[best][i])
				ok = 1;

			if (ok)
			{
				curr |= (1 << i);
				best = i;
				path.push_back(best);
				break;
			}
		}
	}

	path.push_back(0);
	FOR(i, 0, SZ(path))
	{
		if (i)
			cout << " ";
		cout << path[i] + 1;
	}

	exit(0);
}

pair<int, VI> combine()
{
	int old = n;
	n = M;
	FILL(DP, -1);
	int best = -1, ans = INF;
	FOR(i, 1, n)
	{
		int r = solve(1 + (1 << i), i) + d[0][i];
		if (r < ans)
		{
			ans = r;
			best = i;
		}
	}

	VI path;
	used[0] = used[best] = 1;

	path.push_back(0);
	path.push_back(best);
	int curr = 1 + (1 << best);

	while (curr != (1 << n) - 1)
	{
		FOR(i, 0, n)
		{
			if (curr & (1 << i))
				continue;

			bool ok = 0;

			if (solve(curr | (1 << i), i) == solve(curr, best) - d[best][i])
				ok = 1;

			if (ok)
			{
				curr |= (1 << i);
				best = i;
				used[best] = 1;
				path.push_back(best);
				break;
			}
		}
	}

	curr = path.back();
	n = old;
	while (1)
	{
		bool ok = 0;
		FOR(i, 0, n)
			if (used[i] == 0)
				ok = 1;

		if (!ok)
		{
			ans += d[curr][0];
			path.push_back(0);
			break;
		}

		int best = -1;
		FOR(i, 0, n)
		{
			if (used[i])
				continue;
			if (best == -1 || d[curr][best] > d[curr][i])
				best = i;
		}

		ans += d[curr][best];
		path.push_back(best);
		curr = best;
		used[best] = 1;
	}


	return MP(ans, path);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);

	clock_t cl = clock();
	cin >> n;
	FOR(i, 0, n)
		FOR(j, 0, n)
		cin >> d[i][j];

	if (n <= M)
		brute();

	srand(time(NULL) ^ mod);
	pair<int, VI> ans = greedy();
	pair<int, VI> cmb = combine();
	if (cmb.X > ans.X)
		ans = cmb;

	VI per;
	FOR(i, 0, n)
		per.push_back(i);

	while (clock() - cl >= CLOCKS_PER_SEC * 0.97)
	{
		random_shuffle(ALL(per));
		int cnt = d[per[n - 1]][per[0]];
		FOR(i, 0, n - 1)
			cnt += d[per[i]][per[i + 1]];

		if (cnt < ans.X)
		{
			ans.X = cnt;
			ans.Y = per;
			ans.Y.push_back(per[0]);
		}
	}

	cout << ans.X << endl;
	FOR(i, 0, SZ(ans.Y))
	{
		if (i)
			cout << " ";
		cout << ans.Y[i] + 1;
	}

	cin >> n;
	return 0;
}