// LDVSOFT team

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>

#define NAME "salesman"

using namespace std;

//#undef DEBUG

#ifdef HOME
    #define DEBUG_INTER
#endif

#ifdef DEBUG_INTER
    #define iprintf(...) printf("OUT:" __VA_ARGS__ ), fflush(stdout)
#else
    #define iprintf(...) printf( __VA_ARGS__ ), fflush(stdout)
#endif

#ifdef DEBUG
    #define eprintf(...) printf( __VA_ARGS__ ), fflush(stdout)
#else
    #define eprintf(...)
#endif

#ifdef WIN32
    #define LLC "%I64d"
    #define ULLC "%I64u"
#else
    #ifdef WIN64
        #define LLC "%I64d"
        #define ULLC "%I64u"
    #else
        #define LLC "%lld"
        #define ULLC "%llu"
    #endif
#endif

#define pb push_back
#define mp make_pair
#define scn second
#define frs first
#define ins insert

template <typename A>
using setit = typename set<A>::iterator;
template <typename A, typename B>
using mapit = typename map<A, B>::iterator;

using uchar = unsigned char;
using uint  = unsigned int;
using ll    =          long long;
using ull   = unsigned long long;
using ld    =          long double;

using pii = pair<int, int>;

int const N(19);
int const MASK(1 << N);
int const INF(2e9);

int n, Mask;
int a[N][N];
int d[N][MASK], back[N][MASK];

int main(void)
{
    assert(freopen(NAME".in", "r", stdin));
    assert(freopen(NAME".out", "w", stdout));

    scanf("%d", &n);
    Mask = 1 << n;
    for (int i(0); i < n; ++i)
        for (int j(0); j < n; ++j)
            scanf("%d", &a[i][j]);

    for (int mask(0); mask < Mask; ++mask)
        for (int i(0); i < n; ++i)
        {
            if ((mask & (1 << i)) == 0)
                continue;
            int altmask(mask ^ (1 << i));
            if (altmask == 0)
            {
                d[i][mask] = 0;
                back[i][mask] = -1;
            }
            else
            {
                d[i][mask] = +INF;
                for (int j(0); j < n; ++j)
                {
                    if ((altmask & (1 << j)) == 0)
                        continue;
                    if (d[i][mask] <= d[j][altmask] + a[j][i])
                        continue;
                    d[i][mask] = d[j][altmask] + a[j][i];
                    back[i][mask] = j;
                }
            }
            eprintf("! d[ %d ][ %d ] = %d (%d)\n", i, mask, d[i][mask], back[i][mask]);
    }

    int ans(-1);
    for (int i(0); i < n; ++i)
        if (ans == -1 || d[ans][Mask - 1] > d[i][Mask - 1])
            ans = i;

    printf("%d\n", d[ans][Mask - 1]);
    vector<int> an;
    int mask(Mask - 1);
    while (mask)
    {
        an.pb(ans);
        int newMask = mask ^ (1 << ans);
        int newAns = back[ans][mask];
        mask = newMask;
        ans = newAns;
    }
    reverse(an.begin(), an.end());
    for (int i: an)
        printf("%d ", i + 1);

    return 0;
}