rt

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#pragma G++ optimize(3)
using namespace std;
struct node{
	ll to,next,w;
}e[40010];
ll h[40010],cnt=0,u,dis[1010],a,b,c,n,m,pre[1010];
bool vis[1010];
void add(int u,int v,int w)
{
	e[++cnt].to=v;
	e[cnt].next=h[u];
	e[cnt].w=w;
	h[u]=cnt;
}
void dij(int u)
{
	memset(dis,0x3f,sizeof(dis));
	priority_queue<pair<ll,ll> >z;
	dis[u]=0;
	z.push({0,u});
	while(z.size())
	{
		int now=z.top().second;
		z.pop();
		if(vis[now])continue;
		vis[now]=1;
		ll k=dis[now];
		for(int i=h[now];i;i=e[i].next)
		{
			int j=e[i].to;//cout<<j<<" "<<dis[j]<<" "<<dendl;
			if(dis[j]+pre[j]>k+e[i].w+max(e[i].w,pre[now]))
			{
				dis[j]=k+e[i].w;
				pre[j]=max(e[i].w,pre[now]);
				z.push({-dis[j],j});
			}
		}
	}
		if(dis[n]==0x3f3f3f3f)cout<<2147483647<<" ";
		else cout<<dis[n]+pre[n];
}
int main ()
{
	memset(h,-1,sizeof(h));
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	dij(1);
    return 0;
}