T313508 90……

#include<bits/stdc++.h>
using namespace std;
const int xx=1e4+5;
struct www{
	long long y,w;
};
bool operator <(www x,www y){
	return x.w>y.w;
}
long long gai[xx];
long long a[xx][xx];
long long dis[xx],book[xx],dis3[xx],dis1[xx],dis2[xx],dis5[xx];
priority_queue <www> q;long long n,m;
void read(long long &af) {
	long long w=0, f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) w=(w<<3)+(w<<1)+(ch^48);
	af=w*f;
}
void w(long long af) {
	if(af<0) putchar('-'),af=-af;
	if(af>9) w(af/10);
	putchar(af%10+'0'); 
}
void dfs(long long p){
	dis[p]=0;
	q.push({p,dis[p]});
	while(!q.empty()){
		www yy=q.top();
		q.pop();
		long long x=yy.y;
		book[x]=1;
		for(long long i=1;i<=n;i++){
			if(!a[x][i]) continue;
			if(book[i]) continue;
			if(dis[i]>dis[x]+a[x][i]){
				dis1[i]=min(dis1[i],dis[i]);
				dis[i]=dis[x]+a[x][i];
				q.push({i,dis[i]});
			}
		    if(dis[x]+a[x][i]<dis1[i]&&dis[i]<dis[x]+a[x][i]){
				dis1[i]=min(dis1[i],dis[x]+a[x][i]);
				q.push({i,dis[i]});
			}
			if(dis1[x]+a[x][i]<dis1[i]){
				dis1[i]=min(dis1[i],dis1[x]+a[x][i]);
				q.push({i,dis[i]});
			}
		}
	}
}
void dfs3(long long p){
	while(!q.empty()) q.pop();
	dis5[p]=0;
	q.push({p,dis5[p]});
	while(!q.empty()){
		www yy=q.top();
		q.pop();
		long long x=yy.y;
		book[x]=1;
		if(book[n]==1) return;
		for(long long i=1;i<=n;i++){
			if(!a[x][i]) continue;
			if(book[i]) continue;
			if(dis5[i]>dis5[x]+a[x][i]){
				dis5[i]=dis5[x]+a[x][i];
				q.push({i,dis5[i]});
		}
		}
	}
}
void dfs2(long long p){
	dis2[p]=0;
	q.push({p,dis2[p]});
	while(!q.empty()){
		www yy=q.top();
		q.pop();
		long long x=yy.y;
		book[x]=1;
		for(long long i=1;i<=n;i++){
			if(!a[x][i]) continue;
			if(book[i]) continue;
			if(dis2[i]>dis2[x]+a[x][i]){
				dis3[i]=min(dis3[i],dis2[i]);
				dis2[i]=dis2[x]+a[x][i];
				q.push({i,dis2[i]});
			}
		    if(dis2[x]+a[x][i]<dis3[i]&&dis2[i]<dis2[x]+a[x][i]){
				dis3[i]=min(dis3[i],dis2[x]+a[x][i]);
				q.push({i,dis2[i]});
			}
			if(dis3[x]+a[x][i]<dis3[i]){
				dis3[i]=min(dis3[i],dis3[x]+a[x][i]);
				q.push({i,dis2[i]});
			}
		}
	}
}
int main(){
//	freopen("2.in","r",stdin);
//    freopen("ans2.out","w",stdout);
	read(n);
	read(m);
	for(long long i=1;i<=n;i++){
		dis[i]=1e12+5;
		dis1[i]=1e12+5;
		dis2[i]=1e12+5;
		dis5[i]=1e12+5;
	}
	long long x,y;long long z;
	for(long long i=1;i<=m;i++){
		read(x),read(y),read(z);
	
		
		a[x][y]=z;
		a[y][x]=z;
	}
//	if(n<=100&&m<=600){
//		dfs2(1);
//		long long cnt=0;
//		long long hh=dis2[n];
//		for(long long i=1;i<=n;i++){
//		dis[i]=1e12+5;
//		dis1[i]=1e12+5;
//		dis2[i]=1e12+5;
//		book[i]=0;
//	    }
//		for(long long  i=1;i<=n;i++){
//			for(long long j=1;j<=n;j++){
//				if(a[i][j]){
//					a[i][j]*=2;
//					a[j][i]*=2;
//					dfs2(1);
//					cnt=max(cnt,dis2[n]-hh);
//					for(long long i=1;i<=n;i++){
//		            dis[i]=1e12+5;
//	             	dis1[i]=1e12+5;
//		            dis2[i]=1e12+5;
//		            book[i]=0;
//	                }
//					a[i][j]/=2;
//					a[j][i]/=2;
//				}
//			}
//		}
//		cout<<cnt;
//		return 0;
//	}
	dfs(1);
	memset(book,0,sizeof(book));
	dfs2(n);
	long long cnt=0;
	long long f=0;long long lll;
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=n;j++){
		
				if(a[i][j]&&dis1[i]+dis3[j]+a[i][j]==dis1[n]&&dis[i]+dis2[j]+a[i][j]==dis[n]&&a[i][j]>cnt){
					a[i][j]<<=1;
					a[j][i]<<=1;
					memset(book,0,sizeof(book));
					dfs3(1);
					cnt=max(cnt,dis5[n]-dis[n]);
					a[i][j]>>=1;
					a[j][i]>>=1;
					f=1;
					lll=dis5[n]-dis[n];
				}
				else if(a[i][j]&&dis[i]+dis2[j]+a[i][j]==dis[n]&&dis[n]+a[i][j]<=dis1[n]){
					cnt=max(cnt,a[i][j]);
				}
	 		    else if(a[i][j]&&dis[i]+dis2[j]+a[i][j]==dis[n]&&dis[n]+a[i][j]>dis1[n])
	 		    cnt=max(cnt,dis1[n]-dis[n]);
		}
	}
	w(cnt);
}