#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge
{
	int v,w;
};
int n,m,from[5001],mark[5001],vis[5001],dis[5001],road[5001],c=0,x,y;
bool f;
//c表示路径边数，road[i]表示最短路径上的边所出发的点，from[i]表示在最短路上某个点之前的那个点,mark[i]表示最短路径上的点所对边的编号
vector<edge> g[101];
void spfa()
{
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	vis[1]=1,dis[1]=0;
	queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
 		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i].v,w=g[u][i].w;
			if((x==u&&y==v)||(x==v&&y==u))w*=2;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(!f)from[v]=u,mark[u]=i;//是第一次spfa就更新
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	spfa();
	f=1;
	int now=n;
	while(now!=1) 
	{
		c++; 
		road[c]=from[now];
		now=from[now];
	}
	int ans=dis[n],star=dis[n];
	for(int i=1;i<= c;i++)
	{
		
		x=road[i],y=g[road[i]][mark[road[i]]].v;
		spfa();
		ans=max(ans,dis[n]);
	}
	cout<<ans-star;
	return 0;
}