#include<iostream>
#include<algorithm>
#include<string.h>
#define inf 999999999;
using namespace std;
int vis[1001],dis[1001];
int u[1001],v[1001];
int first[100001],next[100001],w[100001];
int pr[1001];
int q[600001];
int way[1001];
int main(){
int n;
cin>>n;
int b=0,a=0;
memset(first,-1,sizeof(first));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>a;
if(a!=0){
b++;
v[b]=i;
u[b]=j;
next[b]=first[i];
first[i]=b;
w[b]=a;
}
}
/* for(int i=1;i<=b;i++){
cout<<node1[i]<<" "<<node2[i]<<" "<<w[i]<<" "<<first[i]<<" "<<next[i]<<endl;
}*/
dis[1]=0;
for(int i=2;i<=n;i++) dis[i]=inf;
vis[1]=1;
int head=1,tail=2;
q[head]=1;
while(head<tail){
int k=first[q[head]];
while(k!=-1){
if(dis[u[k]]>dis[v[k]]+w[k]){
dis[u[k]]=dis[v[k]]+w[k];
pr[u[k]]=v[k];
if(!vis[u[k]]){
q[tail]=u[k];
tail++;
vis[u[k]]=1;
}
}//注意一定是对后节点进行更新
k=next[k];

}
vis[q[head]]=0;
head++;
}
int x=n,ans=0;
while(x!=0){
way[ans]=x;
x=pr[x];
ans++;
}
for(int i=ans-1;i>=0;i--)
cout<<way[i]<<" ";
cout<<endl;
cout<<dis[n];
return 0;
} //SPFA纠结升级版最短路外加求线路，真崩溃呗 <:"-":>