Dijkstra

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define endl '\n'
#define mp make_pair
#define mii map<ll, ll>
#define pii pair<ll, ll>
#define vi vector<ll>
#define vvi vector<vi>
#define vb vector<bool>
#define pii_pq_min  
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define REP(i, a, b) for (ll i = a; i < b; i++)
#define MOD (ll)(1e9 + 7)
#define mod (ll)998244353
void fast()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
long long my_sqrt(long long a)
{
    long long l=0,r=5000000001;
    while(r-l>1)
    {
        long long mid=(l+r)/2;
        if(1ll*mid*mid<=a)l=mid;
        else r=mid;
    }
    return l;
}
bool cmps(pii &a, pii &b)
{
    return a.ss < b.ss;
}
void solve()
{
    ll n,m;cin>>n>>m;
    // vector<pair<pii,ll>> edge(m);
    vector<vector<pii>> adj(n+1);
    REP(i,0,m)
    {
        ll u,v,w;cin>>u>>v>>w;
        // edge.pb({{u,v},w});
        adj[u].pb({v,w});
    }
    vi noDiscount(n+1,LONG_LONG_MAX);
    vi discount(n+1,LONG_LONG_MAX);
    discount[1] = 0;
    noDiscount[1] = 0;
    auto compare = [](const pair<ll, pair<ll, ll>>& a, const pair<ll, pair<ll, ll>>& b) {
        return a.first > b.first;  // Change to a.first < b.first for minimum priority
    };
 
    // Declare a priority queue with the custom comparison function
    priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, decltype(compare)> q(compare);
    // priority_queue<pair<ll,pii> , vector<pair<ll,pii>>, greater<pii>> q;
    q.push({0,{1,1}});
    q.push({0,{1,0}});
    vb discountVisited(n+1,false);
    vb noDiscountVisited(n+1,false);
    ll countDiscount = 0;
    ll countNoDiscount = 0;
    while(!q.empty())
    {
        ll prevDistance = q.top().ff;
        ll isDiscounted = q.top().ss.ss;
        ll u = q.top().ss.ff;
 
        if(discountVisited[u] && noDiscountVisited[u]){
            q.pop();
            continue;
        }
        if(isDiscounted)
        {
            countDiscount++;
            discountVisited[u] = 1;
        }
        else
        {
            noDiscountVisited[u] = 1;
            countNoDiscount++ ;
        }
        
        for (auto x : adj[u])
        {
            if(isDiscounted)
            {
                if(prevDistance + x.ss < discount[x.ff])
                {
                    discount[x.ff] = min<ll>(discount[x.ff] , prevDistance + x.ss);
                    q.push({discount[x.ff],{x.ff,1}}) ; 
                }
                
            }
            else
            {
                //current discounted
                ll currentDiscounted = prevDistance + x.ss/2 ;
                if(currentDiscounted < discount[x.ff])
                {
                    discount[x.ff] = currentDiscounted ;
                    q.push({discount[x.ff],{x.ff,1}});
                }
                // no discount 
                ll currentCost = prevDistance + x.ss;
                if(currentCost < noDiscount[x.ff])
                {
                    noDiscount[x.ff] = currentCost;
                    q.push({noDiscount[x.ff],{x.ff,0}});
                }
            }
        }
        q.pop();
        if(countNoDiscount == n && countDiscount == n)
        break;
    }
 
    cout<<discount[n];
    return;
}
int main()
{
    fast();
    // ll t;
    // cin >> t;
    // while (t--)
    {
        solve();
        cout << endl;
    }
    return 0;
}