//从点1到点n，可使其中一条边长度乘2，求最短路最大的增加值
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int a[N][N],dis[N];
bool vis[N];
int n,m,ma=INT_MIN,ans;
int di(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,true,sizeof(vis));
	int now=1;
	dis[1]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(vis[j]&&dis[j]<dis[now]){
				now=j;
			}
		}
		vis[now]=false;
		for(int j=1;i<=n;i++){
			if(a[now][j]){
				dis[j]=min(dis[now]+a[now][j],dis[j]);
			}
		}
	}
	return dis[n];
}
int main(){
	cin>>n>>m;
	int x,y,v;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>v;
		a[x][y]=a[y][x]=v;
	}
	ans=di();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]){
				a[i][j]*=2;a[j][i]*=2;
				ma=max(ma,di()-ans);
				a[i][j]/=2;a[j][i]/=2;
			}
		}
	}
	cout<<ma;
	return 0;
}