#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
const int N = 3e5+10,M = 1e6+10;
int h[N],e[M],ne[M],w[M],idx;
int max1[N],max2[N],dist[N];//distά\xbb\xa4ǰ\xc3\xe6·\xbe\xb6\xb5\xc4\xd7\xeeСƿ\xbe\xb1·
int dist1[N];
int ans[N];
bool st[N];
void add(int a,int b,int c){
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
typedef pair<int, int> PII;
void dij1(){//\xc7\xf3\xd7\xee\xb6\xccƿ\xbe\xb1·
    memset(dist,0x3f,sizeof dist);
    memset(st,false,sizeof st);
    dist[1]=0;
//    st[1]=true;
    priority_queue<PII, vector<PII>, greater<PII>> pq; 
    pq.push({0,1});
    while(pq.size()){
        PII k=pq.top();
        pq.pop();
        int ver=k.second,distance=k.first;
        if(st[ver]) continue;
        st[ver]=true;

        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
//            if(w[i]>dist[j]){
//                dist[j]=w[i];
//                cout<<j<<" "<<dist[j]<<endl;
//                pq.push({dist[j],j});
//            }
			int val=max(dist[ver],w[i]);
//			cout<<j<<" "<<val<<endl;
			if(val<dist[j]){
				dist[j]=val;
//				cout<<j<<" "<<dist[j]<<endl;
				pq.push({dist[j],j});
			}
        }
    }
}

void dij2(){
	memset(dist1,0x3f,sizeof dist1);
    memset(st,false,sizeof st);
    dist1[n]=0;
    priority_queue<PII, vector<PII>, greater<PII>> pq; 
    pq.push({0,n});
    while(pq.size()){
        PII k=pq.top();
        pq.pop();
        int ver=k.second,distance=k.first;
        if(st[ver]) continue;
        st[ver]=true;

        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
//            if(w[i]>dist[j]){
//                dist[j]=w[i];
//                cout<<j<<" "<<dist[j]<<endl;
//                pq.push({dist[j],j});
//            }
			int val=max(dist1[ver],w[i]);
//			cout<<j<<" "<<val<<endl;
			if(val<dist1[j]){
				dist1[j]=val;
//				cout<<j<<" "<<dist[j]<<endl;
				pq.push({dist1[j],j});
			}
        }
    }
} 

//void dij2(){
//    
//    priority_queue<PII, vector<PII>, greater<PII>> pq; 
//    memset(ans,0x3f,sizeof ans);
//    memset(st,false,sizeof st);
//	ans[1]=0;
//    pq.push({0,1});
//        while(pq.size()){
//        PII k=pq.top();
//        pq.pop();
//        int ver=k.second,distance=k.first;
//        if(st[ver]) continue;
//        st[ver]=true;
//        for(int i=h[ver];~i;i=ne[i]){
//            int j=e[i];
//            if(w[i]>=max1[ver]){
//                max2[j]=max1[ver];
//                max1[j]=w[i];
////                if(dist[j]<max2[j]){
////                    max2[j]=dist[j];
////                }
////                if(max1[j]+max2[j]<ans[j]){
////                    ans[j]=max1[j]+max2[j];
////                    pq.push({ans[j],j});
////                }
//            }else if(w[i]>=max2[ver]){
//                max2[j]=w[i];
//                max1[j]=max1[ver];
////                if(dist[j]<max1[j]){
////                    max1[j]=dist[j];
////                }
////                if(max1[j]+max2[j]<ans[j]){
////                    ans[j]=max1[j]+max2[j];
////                    pq.push({ans[j],j});
////                }
//            }else{
//                max1[j]=max1[ver],max2[j]=max2[ver];
////                if(max1[j]+max2[j]<ans[j]){
////                    ans[j]=max1[j]+max2[j];
////                    pq.push({ans[j],j});
////                }
//            }
//            if(w[i]>=dist[j]){
//            	max1[j]=w[i],max2[j]=dist[j];
//			}else if(w[i]>=max2[i]{
//				max1[j]
//			}
//            if(max1[j]+max2[j]<ans[j]){
//            	if(j==4) cout<<"--"<<max1[j]<<" "<<max2[j]<<endl;
//            	ans[j]=max1[j]+max2[j];
//            	cout<<j<<" "<<ans[j]<<endl;
//            	pq.push({ans[j],j});
//			}
//            
//            
//        }
////        cout<<max1[1]<<"---"<<max2[1]<<endl;
//    }
//}
int main(){
	memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    dij1();
    dij2();
    int ans=0x3f;
	for(int i=2;i<=n-1;i++){
//		cout<<dist[i]<<"---"<<dist1[i]<<endl;
		ans=min(ans,dist[i]+dist1[i]);
	}
	cout<<ans<<endl;
    
}