#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e6+100;

vector<pair<int,int>>nx[N];

ll d[N],flag[N];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        nx[u].push_back({v,w});
        nx[v].push_back({u,w});
    }
    memset(d,0x3f3f3f3f3f3f3f3f,sizeof d);
    priority_queue<pair<pair<ll,pair<ll,ll>>,ll>,vector<pair<pair<ll,pair<ll,ll>>,ll>>,greater<pair<pair<ll,pair<ll,ll>>,ll>>>q;
    q.push({{0,{0,0}},1});
    d[1]=0;
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        auto [t1,id]=t;
        auto [su,t2]=t1;
        auto [ma1,ma2]=t2;
        if(flag[id])
        {
            continue;
        }
        flag[id]=1;
        for(auto [i,j]:nx[id])
        {
            if(flag[i])
            {
                continue;
            }
            ll sign,sign1,sign2;
            if(j>=ma1)
            {
                sign1=j;
                sign2=ma1;
            }
            else if(j>=ma2)
            {
                sign1=ma1;
                sign2=j;
            }
            else{
                sign1=ma1;
                sign2=ma2;
            }
            sign=sign1+sign2;
            if(d[i]<sign)
            {
                continue;
            }
            d[i]=sign;
            q.push({{d[i],{sign1,sign2}},i});
        }
    }
    cout<<d[n]<<endl;
    //system("pause");
    return 0;
}