#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>node[2000009];

map<array<int,3>,int>dis;
const int maxn=3e9+7;

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
       int a,b,w;
       scanf("%d%d%d",&a,&b,&w);
       node[a].push_back(make_pair(b,w));
       node[b].push_back(make_pair(a,w));
    }
    queue<array<int,4>>qq;
    //priority_queue<array<int,4>,vector<array<int,4>>,greater<array<int,4>>>qq;
    //qq.push({0,0,0,0});
   // for(int i=1;i<=n;i++)
   // {
       //dis[i]=3e9+7;
   // }
    //dis[1]=0;
    qq.push({0,1,0,0});
    //dis[{1,0,0}]=1;
    int juli=maxn;
    while(!qq.empty())
    {
       auto [val,nd,fst,lst]=qq.front();
       qq.pop();
       if(dis[{nd,fst,lst}]==1) continue;
       dis[{nd,fst,lst}]=1;
       for(int i=0;i<node[nd].size();i++)
       {
           int tmpfst=fst,tmplst=lst;
           auto [b,w]=node[nd][i];
           if(w>=tmpfst)
           {
              tmplst=tmpfst;
              tmpfst=w;
           }
           else if(w>=tmplst)
           {
             tmplst=w;
           }
            if(dis[{b,tmpfst,tmplst}]!=1)
            {
                if(b==n ) juli=min(juli,tmpfst+tmplst);
              qq.push({tmpfst+tmplst,b,tmpfst,tmplst});
            }
           //if(dis[b]>=tmpfst+tmplst)
           //{
            //  dis[b]=tmpfst+tmplst;
            //  qq.push({dis[b],b,tmpfst,tmplst});
           //}
       }
    }
    printf("%d\n",juli);
    return 0;
}