Kommivoager

#include <cstdio>
#include <algorithm>
#define mem(A,X) memset(A,X,sizeof(A))
#define rep(I,B) for (int I=0;I<(B);I++)

using namespace std;

const int N=14;
const int INF=111111111;

int g[N][N],n,f[N][1<<N],ans=INF,p[N][1<<N],pos;

int calc(int last,int mask){
    if (f[last][mask]!=-1) return f[last][mask];
    int &res=f[last][mask];
    mask^=1<<last;
    res=INF;
    rep(i,n) if (mask&(1<<i)){
        int q=calc(i,mask)+g[i][last];
        if (q<res){
            res=q;
            p[last][mask|(1<<last)]=i;
        }
    }
    return res;
}

int main(){
    scanf("%d",&n);
    rep(i,n) rep(j,n) scanf("%d",&g[i][j]);
    int lim=(1<<n)-1;
    mem(f,255);
    f[0][1]=0;
    rep(i,n){
        int q=calc(i,lim)+g[i][0];
        if (q<ans){
            pos=i;
            ans=q;
        }
    }
    printf("%d\n",ans);
    printf("1 ");
    rep(i,n){
        printf("%d ",pos+1);
        int q=pos;
        pos=p[pos][lim];
        lim^=1<<q;
    }
}