#include<bits/stdc++.h>
using namespace std;
 
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
 
vector<vector<pair<ll,ll>>> adj;
vector<bool> vis;
ll dp[100005][2];
ll n,m;
 
ll dfs(ll node,bool flag){
    
    if(node==n-1) return 0;
     
    if(dp[node][flag]!=-1) return dp[node][flag];
    
    vis[node]=true;
    ll k=1e18;
 
    for(auto e:adj[node]){
        
        int child=e.first;
        ll weight=e.ss;
        
        if(!vis[child]){
            if(flag){
                k=min(k,weight/2+dfs(child,false));
                
            }
            k=min(k,weight+dfs(child,flag));
            
        }
        
    }
    
    vis[node]=false;
    
    return dp[node][flag]=k;
    
    
}
 
 
int main(){
    
    cin>>n>>m;
    
    adj.resize(n);
    vis.resize(n);
    
    memset(dp,-1,sizeof dp);
 
   
    for(ll i=0;i<m;i++){
        ll u,v,w; cin>>u>>v>>w;
        adj[u-1].pb({v-1,w});
    }
   
    cout<<dfs(0,true);
    
    return 0;
    
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAogCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgZmYgZmlyc3QKI2RlZmluZSBzcyBzZWNvbmQKIAp2ZWN0b3I8dmVjdG9yPHBhaXI8bGwsbGw+Pj4gYWRqOwp2ZWN0b3I8Ym9vbD4gdmlzOwpsbCBkcFsxMDAwMDVdWzJdOwpsbCBuLG07CiAKbGwgZGZzKGxsIG5vZGUsYm9vbCBmbGFnKXsKICAgIAogICAgaWYobm9kZT09bi0xKSByZXR1cm4gMDsKICAgICAKICAgIGlmKGRwW25vZGVdW2ZsYWddIT0tMSkgcmV0dXJuIGRwW25vZGVdW2ZsYWddOwogICAgCiAgICB2aXNbbm9kZV09dHJ1ZTsKICAgIGxsIGs9MWUxODsKIAogICAgZm9yKGF1dG8gZTphZGpbbm9kZV0pewogICAgICAgIAogICAgICAgIGludCBjaGlsZD1lLmZpcnN0OwogICAgICAgIGxsIHdlaWdodD1lLnNzOwogICAgICAgIAogICAgICAgIGlmKCF2aXNbY2hpbGRdKXsKICAgICAgICAgICAgaWYoZmxhZyl7CiAgICAgICAgICAgICAgICBrPW1pbihrLHdlaWdodC8yK2RmcyhjaGlsZCxmYWxzZSkpOwogICAgICAgICAgICAgICAgCiAgICAgICAgICAgIH0KICAgICAgICAgICAgaz1taW4oayx3ZWlnaHQrZGZzKGNoaWxkLGZsYWcpKTsKICAgICAgICAgICAgCiAgICAgICAgfQogICAgICAgIAogICAgfQogICAgCiAgICB2aXNbbm9kZV09ZmFsc2U7CiAgICAKICAgIHJldHVybiBkcFtub2RlXVtmbGFnXT1rOwogICAgCiAgICAKfQogCiAKaW50IG1haW4oKXsKICAgIAogICAgY2luPj5uPj5tOwogICAgCiAgICBhZGoucmVzaXplKG4pOwogICAgdmlzLnJlc2l6ZShuKTsKICAgIAogICAgbWVtc2V0KGRwLC0xLHNpemVvZiBkcCk7CiAKICAgCiAgICBmb3IobGwgaT0wO2k8bTtpKyspewogICAgICAgIGxsIHUsdix3OyBjaW4+PnU+PnY+Pnc7CiAgICAgICAgYWRqW3UtMV0ucGIoe3YtMSx3fSk7CiAgICB9CiAgIAogICAgY291dDw8ZGZzKDAsdHJ1ZSk7CiAgICAKICAgIHJldHVybiAwOwogICAgCn0=