rt

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF LONG_LONG_MAX
struct xy
{
	int x,c,l;
}te,te1;
struct edge
{
	int from,to,num;
}tem;
bool operator < (xy qwe,xy wer)
{
	return qwe.c>wer.c;
}
priority_queue<xy> q;
vector<edge> g[114514];
int n,m,t1,t2,t3,t4,t5,dis[114514];
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%lld%lld%lld",&t1,&t2,&t3);
		tem.from=t1;tem.to=t2;tem.num=t3;
		g[t1].push_back(tem);
		tem.from=t2;tem.to=t1;
		g[t2].push_back(tem);
	}
	for(int i=1;i<=n;++i)dis[i]=INF;
	dis[1]=0;
	te.x=1,te.c=0,te.l=0;
	q.push(te);
	while(!q.empty())
	{
		te=q.top();
	//	printf("%lld %lld %lld\n",te.x,te.c,te.l);
		q.pop();
		for(auto i:g[te.x])
		{
			if(dis[te.x]-te.l+max(te.l,i.num)+i.num<dis[i.to])
			{
				te1.x=i.to;
				te1.l=max(te.l,i.num);
				dis[i.to]=dis[te.x]-te.l+max(te.l,i.num)+i.num;
				te1.c=dis[i.to];
				q.push(te1);
			}
		}
	}
	printf("%lld",dis[n]);
	return 0;
}