#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
const int INF=1000000*251;
//ifstream fi("rblock.in");
//ofstream fo("rblock.out");
int N,M;
class EDGE
{
public:
	int u,v,w;
};
vector <EDGE> E;
vector <int> p[251];
int father[251]={0};
int cost,Ans;
int key[251]={0};
bool inq[251]={false};
deque <int> Q;
int SPFA()
{
	memset(inq,false,sizeof(inq));
	for(int i=1;i<=N;i++)
		key[i]=INF;
	key[1]=0;
	Q.clear();
	Q.push_back(1);
	inq[1]=true;
	int a,b,l;
	while(!Q.empty())
	{
		a=Q.front();Q.pop_front();inq[a]=false;
		for(unsigned int i=0;i<p[a].size();i++)
		{
			b=E[p[a][i]].v;l=E[p[a][i]].w;
			if(key[b]<key[a]+l)continue;
			key[b]=key[a]+l;
			father[b]=p[a][i];
			if(inq[b])continue;
			inq[b]=true;
			Q.push_back(b);
		}
	}
	return key[N];
}
int spfa(int change)
{
	memset(inq,false,sizeof(inq));
	for(int i=1;i<=N;i++)
		key[i]=INF;
	key[1]=0;
	Q.clear();
	Q.push_back(1);
	inq[1]=true;
	int a,b,l;
	while(!Q.empty())
	{
		a=Q.front();Q.pop_front();inq[a]=false;
		for(unsigned int i=0;i<p[a].size();i++)
		{
			b=E[p[a][i]].v;l=E[p[a][i]].w;
			if(p[a][i]==change|| p[a][i]==(change^1))l*=2;//加倍
			if(key[b]<key[a]+l)continue;
			key[b]=key[a]+l;
			if(inq[b])continue;
			inq[b]=true;
			Q.push_back(b);
		}
	}
	return key[N];
}
int main()
{
	freopen("rblock.in","r",stdin);
	freopen("rblock.out","w",stdout);
	scanf("%d%d",&N,&M);
	//fi>>N>>M;
	int a,b,l,tot=0;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d%d",&a,&b,&l);
		//fi>>a>>b>>l;
		E.push_back((EDGE){a,b,l});
		p[a].push_back(tot);
		tot++;
		E.push_back((EDGE){b,a,l});
		p[b].push_back(tot);
		tot++;
	}
	cost=SPFA();
	Ans=INF;
	for(int i=father[N];E[i].u!=1;i=father[E[i].u])
	{
		Ans=min(Ans,spfa(i));
	}
	//fo<<Ans-cost<<endl;
	printf("%d\n",Ans-cost);
	return 0;
}