RT

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,a,b,c,ans,h,t,now,nxt;
int head[1005],dis[1005],minn[10005],u[1005];
priority_queue< pair<int,int> >q;
struct AB{
	int a,b,c,n;
}d[40005];
void cun(int a,int b,int c){
	d[++k].a=a,d[k].b=b,d[k].c=c;
	d[k].n=head[a],head[a]=k;
}
int dijkstra(){
	memset(dis,0x3f,sizeof dis);
	memset(minn,0,sizeof minn);
	dis[1]=0;
	minn[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty()){
		now=q.top().second;
		q.pop();
		if(u[now]) continue;
		u[now]=1;
		for(int i=head[now]; i; i=d[i].n){
			nxt=d[i].b;
			if(dis[nxt]+minn[nxt]>dis[now]+d[i].c+max(minn[now],d[i].c)){
				dis[nxt]=dis[now]+d[i].c;
				minn[nxt]=max(minn[now],d[i].c);
				q.push(make_pair(-dis[nxt],nxt));
			}
		}
	}
	return dis[n]+minn[n];
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<=m; i++){
    	scanf("%lld%lld%lld",&a,&b,&c);
    	cun(a,b,c);
    	cun(b,a,c);
	}
	ans=dijkstra();
	printf("%lld",ans);
    return 0;
}