CSES - Flight Discount

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 100;
vector<pair<int64_t,int64_t>> adj[2][maxN];
int64_t dist[2][maxN];

void dijkstra (int64_t source,int64_t n,int64_t type) {
    for (int i = 1; i <= n; ++i) dist[type][i] = LLONG_MAX;
    dist[type][source] = 0;
    priority_queue<pair<int64_t,int64_t>> pq;
    pq.push(make_pair(0,source));
    while (!pq.empty()) {
        int64_t node = pq.top().second;
        int64_t node_cost = abs(pq.top().first);
        pq.pop();
        if (dist[type][node] < node_cost) continue;
        for (pair<int64_t,int64_t> child : adj[type][node]) {
            if (dist[type][child.first] > node_cost + child.second) {
                dist[type][child.first] = node_cost + child.second;
                pq.push(make_pair(-dist[type][child.first],child.first));
            }
        }
    }
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         int n,m;
         cin >> n >> m;
         vector<pair<pair<int64_t,int64_t>,int64_t>> edges;
         for (int i = 1; i <= m; ++i) {
             int64_t u,v,c;
             cin >> u >> v >> c;
             adj[0][u].push_back(make_pair(v,c));
             adj[1][v].push_back(make_pair(u,c));
             edges.push_back(make_pair(make_pair(u,v),c));
         }
         dijkstra(1,n,0);
         dijkstra(n,n,1);
         int64_t res = LLONG_MAX;
         for (pair<pair<int64_t,int64_t>,int64_t> e : edges) {
             int64_t current_edge_cost = e.second;
             int64_t first = e.first.first;
             int64_t second = e.first.second;
             int64_t cost_x = dist[0][first];
             int64_t cost_y = dist[1][second];
             if (cost_x >= LLONG_MAX or cost_y >= LLONG_MAX) {
                 continue;
             }
             res = min(res,cost_x + cost_y + (current_edge_cost / 2));
         }
         cout << res << '\n';
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}