//旅行售货员分支限界法求解
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long

const int N=1e4;
int n;
int ma[N][N];

struct Node{
    int cost;
    int bound;
    vector<int>path;
    bool operator<(const Node&W)const{
        return W.bound<bound;
    }
};


vector<int>bestpath;
int bestans=1e9;
priority_queue<Node>q;


int calbound(Node &node){
    int bound=node.cost;
    vector<int>visit(n+1,0);
    for(int a:node.path){
        visit[a]=1;
    }
    for(int i=1;i<=n;i++){
        if(!visit[i]){
            int minedge=1e9;
            for(int j=1;j<=n;j++){
                if(ma[i][j]&&ma[i][j]<minedge){
                    minedge=ma[i][j];
                }
            }
            bound+=minedge;
        }
    }
    return bound;
}
void bfs(){
    Node start;
    start={0,0,{1}};
    int tmp=calbound(start);
    q.push({0,tmp,{1}});

    while(q.size()){
        auto t=q.top();
        q.pop();
        if(t.bound>=bestans)continue;
        if(t.path.size()==n){
            int ans=t.cost+ma[t.path.back()][1];
            if(ans<bestans){
                bestans=ans;
                bestpath = t.path;

            }
            continue;
        }
        for(int i=1;i<=n;i++){
            if(find(t.path.begin(), t.path.end(), i) != t.path.end()) //要检查的是每次不同的路径，不能用全局变量
                continue;
            //这上面是排掉所有已经访问过的点

            //下面是没有访问过的点
            Node newnode=t;
            newnode.cost+=ma[newnode.path.back()][i];
            newnode.path.push_back(i);
            newnode.bound=calbound(newnode);
            if(newnode.bound<bestans){
                q.push(newnode);
            }
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>ma[i][j];
        }
    }
    bfs();
    cout<<bestans<<endl;
    for(int a:bestpath){
        cout<<a<<" ";
    }
    cout<<"1";
    cout<<endl;
    return 0;
}