Shared code

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

    // cout<<node<<" ";
    
    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;
    
}