#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];
map<pii,int> mm;

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

namespace Seg_tree{
	int s[maxn<<2];
	#define mid ((l+r)>>1)
	#define lson (x<<1),l,mid
	#define rson (x<<1|1),mid+1,r
	void init(int x,int l,int r){
		s[x] = 2e9;
		if(l==r) return ;
		init(lson);init(rson);
	}
	void Modify(int x,int l,int r,int pos,int k){
		s[x] = min(s[x],k);
		if(l==r) return ;
		if(pos<=mid) Modify(lson,pos,k);
		else Modify(rson,pos,k);
	} 
	int Qry(int x,int l,int r,int L,int R){
		if(L<=l&&r<=R){
			return s[x];
		}
		if(R<=mid) return Qry(lson,L,R);
		if(mid<L)  return Qry(rson,L,R);
		return min(Qry(lson,L,R),Qry(rson,L,R));
	}
}
using namespace Seg_tree;

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 = 2e9;
    int v = 2e9;
    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);
    }
    init(1,1,m);
    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(fx==fy) continue;
        if((fx==1&&fy==n)||(fx==n&&fy==1)) break;
        if(fx==1 || fx==n || 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==1&&A[id].b==n) v = min(v,A[id].c);
        		if(A[id].a==n&&A[id].b==1) v = min(v,A[id].c);
			}
            son[fy].push_back(tmp);
        }
        son[fx].clear();
        Ans = min(Ans,A[i].c + v);
    }
    printf("%d\n",Ans);
}

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