#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define mkp make_pair
#define pb push_back
const int INF=1e9+7;
using namespace std;
long long i,n,mask,pos,new_pos,a[15][15],dp[100005][15],j,ans,last_mask,start;
pair < ll, ll  > way[100005][15];
int main()
{
    freopen("aquarium.in","r",stdin);
    freopen("aquarium.out","w",stdout);
    cin>>n;
     for (i=0;i<n;++i)
        for (j=0;j<n;++j)
           {
               cin>>a[i][j];
           }
    for( mask = 0;mask<(1<<n);++mask)
        for( i=0;i<n;++i)
            dp[mask][i] = INF;
    for( i=0;i<n;++i)
        dp[1<<i][i] = 0;
       for (mask=0;mask<(1<<n);++mask)
       {
            for (pos=0;pos<n;++pos)
                if (mask&(1<<pos))
                    for (new_pos=0;new_pos<n;++new_pos)
                        if (!(mask&(1<<new_pos)))
                               if (dp[(mask|(1<<new_pos))][new_pos]>dp[mask][pos]+a[pos][new_pos])
                               {
                                   dp[(mask|(1<<new_pos))][new_pos]=min(dp[(mask|(1<<new_pos))][new_pos],dp[mask][pos]+a[pos][new_pos]);
                                   way[(mask|(1<<new_pos))][new_pos]=mkp(mask,pos);
                               }
       }
    ans = INF;
    for ( i=0;i<n;++i)
    {
        if (ans>dp[(1<<n)-1][i])
                {
                    ans=dp[(1<<n)-1][i];
                    start=i;
                }
    }
     //   ans=min(ans,dp[(1<<n)-1][i]);
    cout<<ans<<endl;
   mask=(1<<n)-1;
   cout<<start+1<<" ";
    for (i=1;i<n;++i)
    {
        last_mask=mask;
        cout<<way[mask][start].s+1<<" ";
        mask=way[mask][start].f;
        start=way[last_mask][start].s;

    }
}