#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;
struct e{
    long long u,v,w,nxt;
}e[maxn];
long long head[maxn],tot,n,m,s,fds[1000010],sds[1000010],vis[1000010];
struct node
{
	long long w,now;
	inline bool operator <(const node& x)const
	{
		return w>x.w;
	}
};
priority_queue<node> q;
void add(long long u,long long v,long long w){
	e[++tot].u=u;
	e[tot].v=v;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}


void dij(){
	memset(fds,127/3,sizeof(fds));
	memset(sds,127/3,sizeof(sds));
	fds[1]=0;
	//sds[s]=0;
	q.push(node{0,1});
	while(!q.empty()){
		cout<<1<<" ";
		node x=q.top();
		q.pop();
		long long u=x.now;
		if(vis[u])continue;
		vis[u]=1;
		int du=e[u].w;
		for(long long i=head[u];i;i=e[i].nxt){
        	int v=e[i].v;
        	
            int w=e[i].w;
            int flag=0;
			if (du+w<fds[v])
                fds[v]=du+w,flag=1;
            if (du+w>fds[v]&&du+w<sds[v])
                sds[v]=du+w,flag=1;
            if (sds[u]+w<sds[v])
                sds[v]=sds[u]+w,flag=1;
			if(flag==1)q.push(node{fds[v],v})	;
		}
	}
} 
int main(){
	cin>>n>>m;
	for(long long i=1;i<=m;i++)
		{
			long long u,v,w;
			cin>>u>>v>>w;
			add(u,v,w);
			add(v,u,w);
		}
	dij();
	cout<<sds[n]<<endl;
	return 0;
}