Shared code

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

typedef long long ll;
#define int ll
#define endl '\n'

const ll mod = 1000000007;
const int inf = INT64_MAX;

signed main()
{
    int n, m;
    cin >> n >> m;

    unordered_map<int, vector<pair<int, int>>> graph;

    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back(make_pair(v, w));
    }

    vector<vector<int>> dist(n + 1, vector<int>(2, inf));

    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.push(make_tuple(0, 1, 0));

    while (!pq.empty())
    {
        int cur_dist, city, used;
        tie(cur_dist, city, used) = pq.top();
        pq.pop();

        if (cur_dist > dist[city][used])
        {
            continue;
        }

        for (const auto &neighbor : graph[city])
        {
            int v = neighbor.first;
            int w = neighbor.second;

            if (used == 0)
            { // try using the ticket
                int new_cost = cur_dist + w / 2;
                if (new_cost < dist[v][1])
                {
                    dist[v][1] = new_cost;
                    pq.push(make_tuple(new_cost, v, 1));
                }
            }

            int new_cost = cur_dist + w;
            if (new_cost < dist[v][used])
            {
                dist[v][used] = new_cost;
                pq.push(make_tuple(new_cost, v, used));
            }
        }
    }

    cout << dist[n][1] << endl;

    return 0;
}