#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;
}