//(～￣▽￣)～    精华内容：链式前向星，dj，美妙的结构体优先队列
#include<bits/stdc++.h>

using namespace std;
int n,m;
struct edge
{
	int w,to,nxt,u;//u起点，w边权，to终点,nxt 
}e[100000];
int head[100000];
int vis[100000];
int dis[100000];
int tis[100000];
int cnt;
void add(int a,int b,int c)
{
	cnt++;
	e[cnt].u=a;
	e[cnt].to=b;
	e[cnt].w=c;
	e[cnt].nxt=head[a];
	head[a]=cnt;	
}
struct eee
{
	int v,w;
	bool 
	operator < (const eee &y)const
	{
		return w > y.w;//此时为小根堆，改成小于号便是大根堆
	} 
};
	priority_queue<eee>q;
void dij()
{
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis)); 
	dis[1]=0; 
	q.push(eee{1,0});
	while(!q.empty())
	{
		int u=q.top().v;//当前执行点的序号
		q.pop();
		vis[u]=1;
		for(int i=head[u];i!=0;i=e[i].nxt)//遍历以u为起点的边
		{
			int v=e[i].to;
			int w=e[i].w;
			if(vis[v]==0)
			{
				if(dis[u]+w<dis[v])
				{
					dis[v]=dis[u]+w;
					q.push(eee{v,dis[v]});
				}
			}
		}
	}
	
}
void tij()
{
	memset(tis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	tis[n]=0;
	q.push(eee{n,0});
	while(!q.empty())
	{
		int u=q.top().v;//当前执行点的序号
		q.pop();
		vis[u]=1;
		for(int i=head[u];i!=0;i=e[i].nxt)
		{
			int v=e[i].to;
			int w=e[i].w;
			if(vis[v]==0)
			{
				if(tis[u]+w<tis[v])
				{
					tis[v]=tis[u]+w;
					q.push(eee{v,tis[v]});
				}
			}
		}
	}
	
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;//起点终点边权
		add(x,y,z);
		add(y,x,z); 
	}
	dij();
	tij();
	int ans=0x3f3f3f3f;
	int mx=dis[n];//最短距离 
	for(int i=1;i<=cnt;i++)
	{
		int a=e[i].u;
		int v=e[i].to;
		int x=dis[a]+e[i].w+tis[v];
		if(x>mx)
		{
			ans=min(ans,x);
		}
	}
	cout<<ans;
}