#include<bits/stdc++.h>
using namespace std;
const int N=300001;
const int M=1000001;
int head[N];
int nexxt[M<<1];
int to[M<<1];
int wei[M<<1];
int cnt=1;
void ege(int a,int b,int c)
{
    to[cnt]=b;
    wei[cnt]=c;
    nexxt[cnt]=head[a];
    head[a]=cnt++;
}
int vis1[N];int vis2[N];
signed main()
{
    int n,m;cin>>n>>m;
    vector<array<int,3>>edge;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;cin>>a>>b>>c;
        edge.push_back({a,b,c});
        ege(a,b,c);ege(b,a,c);
    }
    priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>>que;
    fill(vis1,vis1+n+1,INT_MAX);
    fill(vis2,vis2+n+1,INT_MAX);
    vis1[0]=0;vis2[n]=0;
    que.push({0,1});
    while(!que.empty())
    {
        auto[w,s]=que.top();que.pop();
        if(w>vis1[s])continue;
        for(int i=head[s];i!=0;i=nexxt[i])
        {
            int nt=to[i];
            if(w+wei[i]<vis1[nt])
            {
                vis1[nt]=w+wei[i];
                que.push({vis1[nt],nt});
            }
        }
    }
    que.push({0,n});
    while(!que.empty())
    {
        auto[w,s]=que.top();que.pop();
        if(w>vis2[s])continue;
        for(int i=head[s];i!=0;i=nexxt[i])
        {
            int nt=to[i];
            if(w+wei[i]<vis2[nt])
            {
                vis2[nt]=w+wei[i];
                que.push({vis2[nt],nt});
            }
        }
    }
    int ans=INT_MAX;
    for(auto[a,b,c]:edge)
    {
        if((a==1&&b==n)||(a==n&&b==1))
        {
            ans=min(ans,c);
        }
        int other=min(max(vis1[a],vis2[b]),max(vis1[b],vis2[a]));
        if(other>c)continue;
        ans=min(ans,c+other);

    }
     cout<<ans<<endl;


}