#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[100][100],n,f[100],c[100];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cin>>a[i][j];//输入各个城市之间的费用
        f[i]=10000;//存入的是所有城市到达终点n的最优费用的初始值10000
    }
    f[n]=0;//边界，逆推的起点，n城市到终点费用是0
    for(int i=n-1;i>=1;i--){//逆推开始，依次求f[n-1]到f[1]
        for(int x=i+1;x<=n;x++){//x遍历i+1到n城市是否是最优跳板
            if(a[i][x]>0&&f[x]!=10000){
            // a[i][x]>0代表i城市可以走到x城市
            // f[x]!=10000代表x城市已经求出到底终点的最优值
                if(f[i]>a[i][x]+f[x]){//擂台法求出可以做跳板的城市中费用最低的
                    f[i]=a[i][x]+f[x];
                    c[i]=x;//记录i城市的最优路径
                }
            }
        }
    }
    cout<<"minlong="<<f[1]<<endl;
    int x=1;
    while(x!=0){
        cout<<x<<" ";
        x=c[x];
    }

    return 0;
}

#include<bits/stdc++.h>//头文件 
using namespace std;//命名空间 
const int N=1e4+10;//建一个变量N大小是10010 
int a[100][100],n,f[100],c[100]; //定义数组变量 
int main(){
	cin>>n;//输入 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)cin>>a[i][j];//输入各个城市之间的费用 
		f[i]=10000;// 存入的是所有城市到达终点n的最优费用的初始值10000
	}
	f[n]=0;//边界，逆推的起点，n城市到终点费用是0 
	for(int i=n-1;i>=1;i--){//逆推开始，依次求f[n-1]到f[1] 
		for(int x=i+1;x<=n;x++){//x遍历i+1到n城市是否是最优跳板 
			if(a[i][x]>0&&f[x]!=10000){ 
			//a[i][x]>0代表i城市可以走到x城市
			//f[x]!=10000代表x城市已经求出到底终点的最优值 
				if(f[i]>a[i][x]+f[x]){//擂台法求出可以做跳板的城市中费用最低的 
					f[i]=a[i][x]+f[x];
					c[i]=x;//记录i城市的最优路径 
				}
			}
		}
	}
	cout<<"minlong="<<f[1]<<endl;//输出 
	int x=1;
	while(x!=0){
		cout<<x<<" ";
		x=c[x];
	}
	return 0;
}