RT，WA60pts

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long head[50005],nxt[200005],targetx[200005],targetw[200005],tot;
void add(long long x,long long y,long long w){
	tot++;
	nxt[tot]=head[x];
	head[x]=tot;
	targetx[tot]=y;
	targetw[tot]=w;
}
long long x,y,w;
struct node{
	long long id,dis;
	bool operator <(const node &a)const{
		return a.dis<dis;
	}
};
long long dis[50005],f[50005];
bool vis[50005];
priority_queue<node> q;
void dij(long long *dis){
	memset(vis,0,sizeof(vis));
	q.push({1,dis[1]});
	while(q.size()){
		long long x=q.top().id;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(long long i=head[x];i;i=nxt[i]){
			long long y=targetx[i],w=targetw[i];
			if(dis[x]+w<dis[y]){
				dis[y]=dis[x]+w;
				q.push({y,dis[y]});
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(long long i=1;i<=m;i++){
		cin>>x>>y>>w;
		add(x,y,w);
		add(y,x,w);
	}
	memset(dis,0x7f,sizeof(dis));
	dis[1]=0;
	dij(dis);
	memset(f,0x7f,sizeof(f));
	for(long long x=1;x<=n;x++){
		for(long long i=head[x];i;i=nxt[i]){
			long long y=targetx[i],w=targetw[i];
			if(dis[x]+w<f[y] && dis[x]+w>dis[y]){
				f[y]=dis[x]+w;
			}
		}
	}
	dij(f);
	cout<<f[n];
	return 0;
}