#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<functional>
#include<utility>
#include<cmath>
using namespace std;
struct node{
    long long v,w;  
};
const long long N=10000,INF=1000000000000;
long long n,r,vis[N],di[N],d[N],ans=1000000000000;
vector<node> e[N];
void dijkstra(long long s){
    priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> q;
    for(int i=1;i<=n;i++){di[i]=INF;vis[i]=0;}
    di[s]=0;
    q.push({0,s});
    while(!q.empty()){
        long long u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto i:e[u]){
            long long v=i.v,w=i.w;
            if(di[v]>di[u]+w){
                di[v]=di[u]+w;
                q.push({di[v],v});
            }
        }
    }
}
int main(){
    cin>>n>>r;
    long long u,v,w;
    for(int i=1;i<=r;i++){
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    dijkstra(r);
    for(int i=1;i<=n;i++){
        d[i]=di[i];
    }
    dijkstra(1);
    for(int i=1;i<=n;i++){
        for(auto j:e[i]){
            if(di[i]+d[j.v]+j.w>di[n]){
                ans=min(ans,di[i]+d[j.v]+j.w);
            }
        }
    }
    cout<<ans;
    return 0;
}