#include<iostream>
#include<cstdio>
using namespace std;
int pa[251][251]={0};//pa[x][y]为x到y的邻接矩阵
int path[251]={0};
int fin=0,num;
int father[251]={0};
int N,M,x,y,val;
int i;
int sum=0;
int ans=0;
int fath=0;
bool view[251]={0};
void init()
{
	freopen("rblock.in","r",stdin);
	cin>>N>>M;
	for(i=1;i<=M;i++)
	{	
		cin>>x>>y>>val,pa[x][y]=val,pa[y][x]=val;
	}
}
void dij(int point)
{
	for(i=1;i<=N;i++)
	{
		if(i!=point)//不带自己
		{
			if(pa[point][i]!=0)//有边连接
			{
				if(!path[i])
					father[i]=point,path[i]=path[point]+pa[point][i],fin++;//首次发现
				if(path[point]+pa[point][i]<path[i])
					father[i]=point,path[i]=path[point]+pa[point][i];//更新值
			}
		}
	}
	view[point]=1;
	for(i=1;i<=N;i++)
	{
		if(i!=point)
			{if(pa[point][i]!=0&&view[i]!=1)//有边连接
				dij(i);
			}
	}
}
void dij1(int point)
{
	for(i=1;i<=N;i++)
	{
		if(i!=point)//不带自己
		{
			if(pa[point][i]!=0)//有边连接
			{
				if(!path[i])
					path[i]=path[point]+pa[point][i],fin++;//首次发现
				if(path[point]+pa[point][i]<path[i])
					path[i]=path[point]+pa[point][i];//更新值
			}
		}
	}
	view[point]=1;
	for(i=1;i<=N;i++)
	{
		if(i!=point)
			{if(pa[point][i]!=0&&view[i]!=1)//有边连接
				dij(i);
			}
	}
}
void ke()
{
	for(i=1;i<=250;i++)
		path[i]=0,view[i]=0;
	path[1]=0;
}
void findfather(int point)
{
	if(point!=1)
	{
		fath=father[point];
		pa[fath][point]*=2,pa[point][fath]*=2;
		ke();
		dij1(1);
		ans=max(ans,path[N]-sum);
		pa[fath][point]/=2,pa[point][fath]/=2;
	findfather(fath);
	}
	return;
}
void out()
{
	freopen("rblock.out","w",stdout);
	cout<<ans<<endl;
}
int main()
{
	init();
	path[1]=0;
	dij(1);
	sum=path[N];
	findfather(N);
	out();
}