Dijkstra's Algorithm

using ll = long long;
using pll = pair<ll, int>;
const ll INF = 1e18;

vector<ll> dijkstra(int start, const vector<vector<pair<int, ll>>> &g) {
    int n = g.size();
    vector<ll> dist(n, INF);
    priority_queue<pll, vector<pll>, greater<>> pq;
    dist[start] = 0;
    pq.emplace(0, start);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto &[v, w] : g[u])
            if (dist[v] > dist[u] + w)
                pq.emplace(dist[v] = dist[u] + w, v);
    }
    return dist;
}