#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
char ra;
int rp=0;
inline void read(int &x)
{
	x&=0;
	rp=1;
	ra=getchar();
	while(ra<'0'||ra>'9') 
	{
		if(ra=='-') rp=-1;
		ra=getchar();
	}
	while(ra>='0'&&ra<='9') 
	{
		x=(x<<3)+(x<<1)+(ra^48);
		ra=getchar();
	}
	x*=rp;
} 
inline void write(int x)
{
	if(x/10) write(x/10);
	putchar(x%10+48);
}
///////////
const int N=5005;
const int M=100005;
int sl[N][N];
int nc;
int mc;
int st[N];
struct T
{
	int p;
	int ar;
	int nx;
}a[M<<1];
int aj;
inline void ADD(int x,int y,int z)
{
	a[++aj].ar=y;
	a[aj].p=z;
	a[aj].nx=x[st];
	x[st]=aj;
	return;
}
int ans[N];
int asp[N];//最短路中的最短边 
queue<int> d;
int pd[N];//判断是否在队中 
int fa[N];
void SPFA()
{
	int cl=d.front();
	d.pop();
	for(int i=st[cl],sr;i;i=a[i].nx)
	{
		sr=a[i].ar;
		if(ans[sr]>ans[cl]+a[i].p)
		{
			d.push(sr);
			ans[sr]=ans[cl]+a[i].p;
			asp[sr]=min(asp[cl],a[i].p);
			fa[sr]=cl;
		}
	}
	return;
}
int main()
{
	freopen("roadblocks.in","r",stdin);
	freopen("roadblocks.out","w",stdout);
    read(nc);
    read(mc);
	memset(sl,0x3f,sizeof(sl));
    int s1,s2,s3;
    for(int i=1;i<=mc;i++) 
    {
    	read(s1);
    	read(s2);
    	read(s3);
    	sl[s1][s2]=min(sl[s1][s2],s3);
		sl[s2][s1]=min(sl[s2][s1],s3);
	}
	for(int i=1;i<=nc;i++)
		for(int o=1;o<i;o++)
		if(sl[i][o]!=sl[0][0]) 
		{
			ADD(i,o,sl[i][o]),ADD(o,i,sl[i][o]);
//			cout<<i<<" "<<o<<":"<<sl[i][o]<<endl;
		}
	memset(ans,0x3f,sizeof(ans));
	memset(asp,0x3f,sizeof(asp));
	ans[1]=0;
	d.push(1);
//	cout<<"PA1\n";
	while(d.size()) SPFA();
//	cout<<"PA2\n";
	int out=ans[nc]+(asp[nc]<<1);
//	cout<<out<<endl;
	ans[1]=1<<30;
//	for(int i=1;i<=nc;i++) cout<<"P:"<<i<<" "<<fa[i]<<" "<<ans[i]<<endl;
	for(int i=st[nc];i;i=a[i].nx) if(a[i].ar!=fa[nc]) out=min(out,ans[a[i].ar]+a[i].p);
	write(out);
	putchar(10);
	return 0;
}