CSES – Flight Discount

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 1e5+5;
int n,m,dis[2*maxn];
vector<pii> G[2*maxn];
//
void dijkstra(int start){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({0,start});
    while(pq.size()){
        auto [w,cur] = pq.top(); pq.pop();
        if(dis[cur] != 1e18) continue;
        dis[cur] = w;
        for(auto [adj,weight]: G[cur]){
            pq.push({dis[cur] + weight,adj});
        }
    }
}
signed main(){
    fastio;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c; cin>>a>>b>>c;
        G[a].push_back({b,c});
        G[a+n].push_back({b+n,c});
        G[a].push_back({b+n,c/2});
    }
    for(int i=1;i<=2*n;i++) dis[i] = 1e18;
    dijkstra(1);
    cout<<dis[n+n]<<"\n";
    return 0;
}