#include<cstring>
#include<iostream>
#include<cstdio>

using namespace std;
#define MAXN 255
#define MAXM 50005
int n,m,s,ans,pp;
int p[MAXN],ver[MAXM],edge[MAXM],last[MAXM];
int heap[MAXM],val[MAXM];
bool v[MAXN];
int dis[2][MAXN],dist[MAXN];

void add(int ff,int tt,int ww){
	ver[++s]=tt;
	edge[s]=ww;
	last[s]=p[ff];
	p[ff]=s;
}

void up(int x){
	int i=x>>1;
	if (!i) return ;
	if (val[i]>val[x]){
		swap(val[i],val[x]);
		swap(heap[i],heap[x]);
		up(i);
	}	
}
void down(int x){
	int i=x<<1;
	if (i>pp) return ;
	if (i<pp && val[i+1]<val[i])i++;
	if (val[i]<val[x]){
		swap(val[i],val[x]);
		swap(heap[i],heap[x]);
		down(i);
	}
}
void del(int x){
	heap[x]=heap[pp];val[x]=val[pp];
	pp--;
	down(x);
}
void insert(int x,int y){
	heap[++pp]=x;val[pp]=y;
	up(pp);
}

void DJS(int st){
	int i,x,z;
	if (st==1)z=0;
	else z=1;
	dis[z][st]=0;
	pp=0;
	insert(st,0);
	memset(v,0,sizeof(v));
	while(pp){
		x=heap[1];del(1);
		if (v[x]) continue;
		v[x]=1;
		for (i=p[x];i;i=last[i]){
			if (dis[z][ver[i]]>dis[z][x]+edge[i]){
				dis[z][ver[i]]=dis[z][x]+edge[i];
				insert(ver[i],dis[z][ver[i]]);
			}
		}
	}
}

void DJSST(){
	int i,x;
	memset(dist,50,sizeof(dist));
	dist[1]=0;
	memset(v,0,sizeof(v));
	pp=0;
	insert(1,0);
	while(pp){
		x=heap[1];del(1);
		if (v[x]) continue;
		v[x]=1;
		for (i=p[x];i;i=last[i]){
			if (dist[ver[i]]>dist[x]+edge[i]){
				dist[ver[i]]=dist[x]+edge[i];
				insert(ver[i],dist[ver[i]]);
			}
		}
	}
}

void work(){
	int i;
	for (i=2;i<=s;i++){
		if (dis[0][ver[i ^ 1]]+dis[1][ver[i]]+edge[i]==dis[0][n]){
			edge[i]*=2;
			edge[i ^ 1]=edge[i];
			DJSST();
			ans=max(ans,dist[n]-dis[0][n]);
			edge[i]/=2;
			edge[i ^ 1]=edge[i];
		}
	}
}

int main(){
	freopen("rblock.in","r",stdin);
	freopen("rblock.out","w",stdout);
	int i,ff,tt,ww;
	scanf("%d%d",&n,&m);
	s=1;
	memset(p,0,sizeof(p));
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&ff,&tt,&ww);
		add(ff,tt,ww);
		add(tt,ff,ww);
	}
	memset(dis,50,sizeof(dis));
	DJS(1);
	DJS(n);
	ans=0;
	work();
	printf("%d\n",ans);
	return  0;
}