#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int n,m;
int fro[60000],ver[60000],next[60000],r[300],tot;
long long w[60000];
long long dis1[300],dis2[300];
int pre[300];
long long ans1,ans2;
bool v[300];

long long max(long long a,long long b){
	if (a>b) return a;
	return b;
}
void add(int x,int y,long long z){
	ver[++tot]=y;
	fro[tot]=x;
	w[tot]=z;
	next[tot]=r[x];
	r[x]=tot;
}

void init(){
	int i,x,y;
	long long z;
	scanf("%d%d",&n,&m);
	tot=1;
	memset(r,0,sizeof(r));
	for (i=1;i<=m;i++){
		scanf("%d%d%I64d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
}

void dijkstra1(){
	int i,y,j,k;
	long long temp;
	memset(v,0,sizeof(v));
	for (i=1;i<=n;i++) dis1[i]=1000000000000;
	dis1[1]=0;
	for (i=1;i<=n;i++){
		temp=1000000000000;
		for (j=1;j<=n;j++)
		if (dis1[j]<temp && !v[j]){
			temp=dis1[j];
			k=j;
		}
		v[k]=true;
		for (j=r[k];j;j=next[j]){
			y=ver[j];
			if (dis1[y]>dis1[k]+w[j]){
				dis1[y]=dis1[k]+w[j];
				pre[y]=j;
			}
		}
	}
	ans1=dis1[n];
}
		
void dijkstra2(){
	int i,y,j,k;
	long long temp;
	memset(v,0,sizeof(v));
	for (i=1;i<=n;i++) dis2[i]=1000000000000;
	dis2[n]=0;
	for (i=1;i<=n;i++){
		temp=1000000000000;
		for (j=1;j<=n;j++)
		if (dis2[j]<temp && !v[j]){
			temp=dis2[j];
			k=j;
		}
		v[k]=true;
		for (j=r[k];j;j=next[j]){
			y=ver[j];
			if (dis2[y]>dis2[k]+w[j])
				dis2[y]=dis2[k]+w[j];
		}
	}
}
	
void solve(){
	int i,x,y,j;
	long long temp;
	ans2=0;
	for (i=pre[n];i;i=pre[fro[i]]){
		x=fro[i];y=ver[i];
		temp=w[i]*2+dis1[x]+dis2[y];
		for (j=r[x];j;j=next[j])
		if (j!=i /*&& j!=(pre[x]^1) */&& dis1[x]+dis2[ver[j]]+w[j]<temp)
			temp=dis1[x]+dis2[ver[j]]+w[j];
			
		ans2=max(ans2,temp-ans1);
	}
	printf("%I64d\n",ans2);
}
	
int main(){
freopen("rblock.in","r",stdin);
freopen("rblock.out","w",stdout);
	init();
	dijkstra1();
	dijkstra2();
	solve();
	
	return 0;
}