#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int MAXN=3e5+5,inf=1e18;
int head[MAXN],cnt;
struct edge{
    int to,w,nx;
}e1[MAXN<<1];
void add_edge(int u,int v,int w)
{
    e1[cnt].to=v;
    e1[cnt].w=w;
    e1[cnt].nx=head[u];
    head[u]=cnt++;
}
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n;i++) head[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;cin>>u>>v>>w;
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    queue<int> q;
    priority_queue<int,vector<int>,greater<>> q1;
    vector<int> vis(n+1),vise(cnt+1);
    vector<pair<int,int>> p(n+1,{inf,inf});
    p[1]={0,0};
    q1.push(1);
    vis[1]=1;
    vector<pair<int,int>> e[n+1];
    while(q1.size())
    {
        int u=q1.top();q1.pop();
        // cerr<<u<<endl;
        for(int i=head[u];i!=-1;i=e1[i].nx)
        {
            int v=e1[i].to,w=e1[i].w;
            // cerr<<i<<endl;
            if(vise[i]) continue;
            int pre=p[v].first+p[v].second;
            int minn=min({w,p[u].first,p[u].second});
            int now=w+p[u].first+p[u].second-minn;
            // if(u==5 && v==7) cout<<pre<<' '<<now<<endl;
            if(now<=pre)
            {
                p[v].first=max({p[u].first,p[u].second,w});
                p[v].second=p[u].first+p[u].second+w-p[v].first-min({p[u].first,p[u].second,w});
                e[u].push_back({v,w});
                if(!vis[v]){q1.push(v);vis[v]=1;}
                vise[i]=vise[i^1]=1;
            }
        }
    }
    // for(int i=1;i<=n;i++)
    // {
    //     for(auto v:e[i]) cout<<v.first<<' ';
    //     cout<<endl;
    // }
    vector<int> deg(n+1);
    for(int i=1;i<=n;i++)
        for(auto v:e[i]) deg[v.first]++;
    for(int i=2;i<=n;i++) p[i]={inf,inf};
    q.push(1);
    while(q.size())
    {
        int u=q.front();q.pop();
        for(auto [v,w]:e[u])
        {
            int max1=max({p[u].first,p[u].second,w});
            int max2=p[u].first+p[u].second+w-max1-min({p[u].first,p[u].second,w});
            if(max1+max2<=p[v].first+p[v].second)
            {
                p[v].first=max1;
                p[v].second=max2;
                deg[v]--;
                if(!deg[v]) q.push(v);
            }
        }
    }
    // for(int i=1;i<=n;i++)
    //     cout<<p[i].first<<' '<<p[i].second<<endl;
    cout<<p[n].first+p[n].second<<endl;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t=1;
    while(t--) solve();
    return 0;
}