#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
#define modd(a,b) a=a%b
#define pb push_back
#define db double
#define lowbit(x) x&(-x)
#define cerr(x) cout<<#x<<"="<<x<<endl
const ll mod=1e9+7;
ll ksm(ll a,ll b) {ll ans=1,bs=a;while(b) {if(b&1) ans=ans*bs%mod;bs=bs*bs%mod;b>>=1;}return ans;}
#define fi first
#define se second
#define N 300010
#define M 1000010<<1
int n,m;
int fa[N],tot=0;
int dep[2][N];
ll dis[2][N];
vector<pair<int,ll>>to[N];
struct edge{int x,y;ll w;}e[M],g[M];
void add(int a,int b,ll c) {to[a].pb({b,c});}
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y,ll w) {
    int fx=find(x),fy=find(y);
    if(fx==fy) return;
    fa[fx]=fy;
    g[++tot]=(edge){x,y,w};
}
void solve() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++) {
        int a,b,c;cin>>a>>b>>c;
        e[i]=(edge){a,b,c};
    }
    sort(e+1,e+m+1,[&](edge a,edge b){return a.w<b.w;});
    for(int i=1;i<=m;i++) {
        auto [x,y,w]=e[i];
        merge(x,y,w);
        if(tot==n-1) break;       
    }
    for(int i=1;i<=tot;i++) {
        auto [x,y,w]=g[i];
        add(x,y,w),add(y,x,w);
    }
    auto dfs=[&](auto self,int u,int type,int fa)->void {
        dep[type][u]=dep[type][fa]+1;
        for(auto [v,w]:to[u]) {
            if(v==fa) continue;
            dis[type][v]=dis[type][u]+w;
            self(self,v,type,u);
        }
    };
    dfs(dfs,1,0,0);
    dfs(dfs,n,1,0);
    ll ans=1e18,tmp=0;
    for(int i=1;i<=m;i++) {
        auto [x,y,fir]=e[i];
        if(x==1 && y==n) cmin(ans,fir);
        if(x==n && y==1) cmin(ans,fir);
        ll sec;
        if(dep[0][x]>dep[0][y]) swap(x,y);
        sec=min(dis[0][x]+dis[1][y],dis[1][x]+dis[0][y]);
        cmin(ans,fir+sec);
    }
    // for(int i=1;i<=n;i++) cout<<dis[1][i]<<" ";cout<<endl;    
    cout<<ans<<endl;
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // int T;
    // cin>>T;
    // while(T--) 
    solve();
    return 0;
}
/*
最大值可以看作是枚举当前的最大值然后2个端点分别和1,n进行取max然后加和即可
*/