#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define int long long
typedef long long LL;

inline int read(){
	int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } 
    while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } 
    return x * f ;
}

const int maxn = 1e6+20;
int n,m;
int f[maxn];
vector<int> son[maxn],p[maxn];
struct Node{
    int a,b,c;
    bool operator <(const Node X)const{
        return c < X.c;
    }
}A[maxn];
set<int> s;
set<int>::iterator it;

int find(int x){
    return x==f[x] ? x : find(f[x]);
}

void solve(){
    n = read();m = read();
    for(int i=1;i<=m;i++){
        int a = read(),b = read(),c = read();
        A[i] = (Node){a,b,c};
    }
    sort(A+1,A+1+m);
    if(n==2){
        printf("%d\n",A[1].c);
        return ;
    }
    for(int i=1;i<=n;i++){
        f[i] = i;
        son[i].push_back(i);
    }
    int Ans = 1e18;
    int v = 1e18;
    for(int i=1;i<=m;i++){
        p[A[i].a].push_back(i);
        p[A[i].b].push_back(i+m);
        if(A[i].a==1&&A[i].b==n) Ans = min(Ans,A[i].c);
        if(A[i].a==n&&A[i].b==1) Ans = min(Ans,A[i].c);
    }
    for(int i=1;i<=m;i++){
        int x = A[i].a;
        int y = A[i].b;
        int fx = find(x);
        int fy = find(y);
        if(find(1)==find(n)) break;
		int f1 = find(1);
		int fn = find(n);
        if(fx!=fy){
	        if(son[fx].size() > son[fy].size()){
	            swap(x,y);
	            swap(fx,fy);
	        }
	        f[fx] = fy;
	        for(int tmp : son[fx]){
	            for(int tt : p[tmp]){
	                int id = 0;
	                if(tt > m && tt - m > i){
	                    A[tt-m].b = fy;
	                    id = tt - m;
	                }
	                else if(tt <= m && tt > i){
	                    A[tt].a = fy;
	                    id = tt;
	                }
	                else continue;
	                if(A[id].a==f1&&A[id].b==fn) s.insert(id);
	        		if(A[id].a==fn&&A[id].b==f1) s.insert(id);
				}
	            son[fy].push_back(tmp);
	        }
	        son[fx].clear();
    	}
    	while(s.size() && *s.begin() <= i){
    		it = s.begin();
    		s.erase(it);
		}
		if(s.size()) Ans = min(Ans,A[i].c + A[*s.begin()].c);
    }
    printf("%lld\n",Ans);
}

signed main(){
//	freopen("data.txt","r",stdin);
	int T = 1;
	// T = read();
	while(T--) solve();
	return 0;
}