#include<bits/stdc++.h>
using namespace std;
int n,a[110],b[110];//儿子表示法 
void dfsq(int l){
	cout<<l<<" ";
	if(a[l]!=0) dfsq(a[l]);
	if(b[l]!=0) dfsq(b[l]);
}
void dfsz(int l){
	if(a[l]!=0) dfsz(a[l]);
	cout<<l<<" ";
	if(b[l]!=0) dfsz(b[l]);
}
void dfsh(int l){
	if(a[l]!=0) dfsh(a[l]);
	if(b[l]!=0) dfsh(b[l]);
	cout<<l<<" ";
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	dfsq(1);
	cout<<"\n";
	dfsz(1);
	cout<<"\n";
	dfsh(1);
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+10;
struct node{
	int d,q;
};
ll n,m,dist[N],mk[N];
vector<node> v[N];//邻接表存出边的信息  点和权置 
void Dijkstra(){
	for(int i=1;i<=n;i++) dist[i]=1e9;//初始化无穷大 
	dist[1]=0;
	for(int i=1;i<=n-1;i++){
		//找到距离起点最小的点----找dist数组中的最小值 
		ll min_dist=1e9+10,x=0;
		for(int j=1;j<=n;j++){
			if(mk[j]==0&&dist[j]<min_dist){
				min_dist=dist[j];
				x=j;//保存最小值点 
			}
		} 
		mk[x]=1;//标记一下 
		//遍历x点所有出边点
		for(int j=0;j<v[x].size();j++){
			int xx=v[x][j].d;//
			if(dist[xx]>dist[x]+v[x][j].q) dist[xx]=dist[x]+v[x][j].q; 
		} 
	}
}
int main(){
	cin>>n>>m;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;//x->y的权值z 
		v[x].push_back({y,z});
	}
	Dijkstra();
	if(dist[n]==1e9) dist[n]=-1;
	cout<<dist[n]; 
	return 0;
}

/*
dijkstra 算法---最短路
1.初始化dist数组为无穷大  
2.起点距离设置为0

	循环n-1轮操作
		找所有点中距离起点最近的点x 并且 没有被标记过
		标记x点 
		遍历x点的所有出边点xx  做 松弛操作（更新最短距离）
			判断原来dist[xx] 和 当前x点走过来的距离  谁更小
				小就更新	
*/