#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<pair<ll,ll>>> adj,adj_rev;
vector<ll> d1,d2;
 
void dijkstra(){
    set<pair<ll,ll>> st;
    st.insert({0,1});
    d1[1]=0;
    while(!st.empty()){
        ll node=st.begin()->second;
        st.erase(st.begin());
        for(auto it:adj[node]){
            ll child=it.first,wt=it.second;
            st.erase({d1[child],child});
            if(d1[child]>d1[node]+wt){
                d1[child]=d1[node]+wt;
                st.insert({d1[child],child});
            }
        }
    }
}
 
void dijkstra1(){
    set<pair<ll,ll>> st;
    ll n=adj.size()-1;
    st.insert({0,n});
    d2[n]=0;
    while(!st.empty()){
        ll node=st.begin()->second;
        st.erase(st.begin());
        for(auto it:adj_rev[node]){
            ll child=it.first,wt=it.second;
            st.erase({d2[child],child});
            if(d2[child]>d2[node]+wt){
                d2[child]=d2[node]+wt;
                st.insert({d2[child],child});
            }
        }
    }
}
 
int main(){
    ll n,m;
    cin>>n>>m;
    adj=adj_rev=vector<vector<pair<ll,ll>>>(n+1);
    d1=d2=vector<ll>(n+1,1e18);
    while(m--){
        ll a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj_rev[b].push_back({a,c});
    }
    dijkstra();
    dijkstra1();
    ll ans=1e18;
    for(int i=1;i<=n;i++){
        for(auto it:adj[i]){
            ans=min(ans,d1[i]+d2[it.first]+it.second/2);
        }
    }
    cout<<ans;
    return 0;
}