#include<bits/stdc++.h>
using namespace std;
int n,m,k,maps[201][201],dis[201],mx[201];
bool flag[201];
void dijkstra(int u)
{
	for(int i=1;i<=n;i++)
	{
		if(maps[u][i]!=INT_MAX)
		{
			mx[i]=maps[u][i];
			dis[i]=2*mx[i];
		}
		else
		{
			dis[i]=INT_MAX;
			mx[i]=0;
		}
	}
	dis[u]=0;
	flag[u]=true;
	for(int i=1;i<=n;i++)
	{
		int mn=INT_MAX,t=u;
		for(int j=1;j<=n;j++)
		{
			if(!flag[j]&&mn>dis[j])
			{
				t=j;
				mn=dis[j];
			}
		}
		if(t==u)return;
		flag[t]=true;
		for(int j=1;j<=n;j++)
		{
			if(maps[t][j]<INT_MAX)
			{
				if(maps[t][j]>=mx[t])
				{
					if(2*maps[t][j]+dis[t]-mx[t]<dis[j])
					{
						dis[j]=2*maps[t][j]+dis[t]-mx[t];
						mx[j]=maps[t][j];
					}	
				}
				else if(maps[t][j]<mx[t])
				{
					if(maps[t][j]+dis[t]<dis[j])
					{
						mx[j]=dis[t];
						dis[j]=maps[t][j]+dis[t];
					}
				}
			}
		}
	}
}
int main()
{
	int x,y,v;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			maps[i][j]=INT_MAX;
		}
	}
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>v;
		maps[x][y]=maps[y][x]=v;
	}
	dijkstra(1);
	cout<<dis[n];
	return 0;
}