ks

#include<cstdio>
#include<queue>
using namespace std;
#define re register
#define li(i,j,k) for(re int i=j ; i<=k ; i++)
#define si(i,j,k) for(re int i=j ; i>=k ; i--)
const int MAXM=5000500;
const int MAXN=10050;
const int INF=0x3f3f3f3f;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<3)+(x<<1)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
struct Edge{
    int to,w,next;
};
struct yzy{
    int dist,pos;
    bool operator < (const yzy &x)const{
        return dist>x.dist;
    }
};
Edge e[MAXM];
int head[MAXN];
int tot=0;

bool vis[MAXN];
int pre[MAXN];
int dis[MAXN];

int n,m,s;
int cnt_a,cnt_b;

priority_queue<yzy> q; 

void add(int u,int v,int w){
    tot++;
    e[tot].to=v;
    e[tot].w=w;
    e[tot].next=head[u];
    head[u]=tot;
    return ;
}

int cut_a,cut_b;

yzy aaaa(int a,int b){
	yzy aaa;
	aaa.dist=a,aaa.pos=b;
	return aaa;
}
void dijkstra(int hack){
	if(hack==1){
	    li(i,1,n)dis[i]=INF;
	    li(i,1,n)vis[i]=false;
	    dis[s]=0;
	    q.push(aaaa(dis[s],s));
	    while(!q.empty()){
	        yzy now=q.top();
	        q.pop();
	        int x=now.pos;
	        if(vis[x]) continue;
	        vis[x]=true;
	        for(int i=head[x] ; i ; i=e[i].next){
	        	int v=e[i].to;
	        	if((x==cnt_a && v==cnt_b) || (v==cnt_a && x==cnt_b))continue;
	            if(dis[v]>dis[x]+e[i].w){
	                dis[v]=dis[x]+e[i].w;
	                q.push(aaaa(dis[v],v));
	            }
	        }
	    }
	}else{
	    li(i,1,n)dis[i]=INF;
	    li(i,1,n)vis[i]=false;
	    dis[s]=0;
	    q.push(aaaa(dis[s],s));
	    while(!q.empty()){
	        yzy now=q.top();
	        q.pop();
	        int x=now.pos;
	        if(vis[x]) continue;
	        vis[x]=true;
	        for(int i=head[x] ; i ; i=e[i].next){
	        	int v=e[i].to;
	        	if((x==cnt_a && v==cnt_b) || (v==cnt_a && x==cnt_b))continue;
	            if(dis[v]>dis[x]+e[i].w){
	                dis[v]=dis[x]+e[i].w;
	                pre[v]=x;
	                q.push(aaaa(dis[v],v));
	            }
	        }
	    }
	}
}
int max(int a,int b){
	return a>b?a:b;
}
int main(){
	n=read(),m=read();
    s=1;
    li(i,1,m){
        int u,v,w;
        u=read(),v=read(),w=read();
        add(u,v,w);
        add(v,u,w);
    }
    dijkstra(0);
    int ans=dis[n];
    int i=n;
    while(i){
    	cnt_a=i,cnt_b=pre[i];
    	//printf("cnt%d %d\n",cnt_a,cnt_b);
		//printf("%d %d\n",i,pre[i]);
    	dijkstra(1);
    	ans=max(ans,dis[n]);
		i=pre[i];
	}
	printf("%d",ans);
    return 0;
}