#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define For(i,j,k) for (int i=(j);i<=(k);i++)
#define rof(i,j,k) for (int i=(j);i>=(k);i--)
#define ull unsigned long long
#define lowbit(x) ((x)&(-(x)))
#define PII pair<int,int>
#define int long long
#define endl "\n"
#define ls rt<<1
#define rs rt<<1|1
typedef long long ll;
const int mod = 998244353;
const double eps = 1e-9;
const int N=2e6+7;
int n,m;
typedef struct edge{
    int pos;
    int w;
}edge;
vector<edge> connects[1000001];
void add_edge(int u,int v,int w){
    connects[u].push_back({v,w});
    connects[v].push_back({u,w});
    return ;
}
typedef struct node{
    int pos;
    int dis1;
    int dis2;
    bool operator<(const node &x) const{
        return x.dis1+x.dis2<dis1+dis2;
    }
}node;
map<PII,int> vis;
int dist[1000005];
void Dijikstra(){
    dist[1]=0;
    priority_queue<node> q;
    q.push({1,0,0});
    while(!q.empty()){
        int pos=q.top().pos;
        int dis1=q.top().dis1;
        int dis2=q.top().dis2;
        q.pop();
        if(vis[{pos,dis1+dis2}]) continue;
        vis[{pos,dis1+dis2}]=1;
        for(int i=0;i<connects[pos].size();i++){
            int v=connects[pos][i].pos;
            int w=connects[pos][i].w;
            if(dist[v]>dis1+dis2+w-min(min(dis1,dis2),w)){
                dist[v]=dis1+dis2+w-min(min(dis1,dis2),w);
                if(w<dis1&&w<dis2){
                    q.push({v,dis1,dis2});
                }else if(w>dis1){
                    q.push({v,w,dis1});
                }else if(w>dis2){
                    q.push({v,dis1,w});
                }
            }
        }
    }
}
void solve(){
	cin>>n>>m;
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        add_edge(u,v,w);
    }
    for(int i=0;i<=n;i++) dist[i]=0x3f3f3f3f;
    Dijikstra();
    cout<<dist[n]<<endl;
}
signed main(){
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
}