dijkstra

    REP1(i,n) dis[i] = inf;
    dis[1] = 1;
    priority_queue <pii,vector<pii>,greater<pii>> pq;
    pq.push(mkp(0,1));

    while (!pq.empty()){
        auto [d,x] = pq.top(); pq.pop();

        if (d > dis[x]) continue;

        for (auto [i,w]:adj[x]){
            if (d + w < dis[i]){
                dis[i] = d + w;
                pq.push(mkp(dis[i],i));
            }
        }
    }