#include<ext/pb_ds/priority_queue.hpp>
#define ll long long
#define pa pair<ll,int>
using namespace std;
using namespace __gnu_pbds;
typedef __gnu_pbds::priority_queue<pa,greater<pa>,pairing_heap_tag > heap;
heap::point_iterator id[1000005];

    heap q;
    dis[1]=0;id[1]=q.push(make_pair(0,1));
    while(!q.empty())
    {
        int now=q.top().second;q.pop();
        for(int i=last[now];i;i=e[i].next)
            if(e[i].v+dis[now]<dis[e[i].to])
            {
                dis[e[i].to]=e[i].v+dis[now];
                if(id[e[i].to]!=0)
                    q.modify(id[e[i].to],make_pair(dis[e[i].to],e[i].to));
                else id[e[i].to]=q.push(make_pair(dis[e[i].to],e[i].to));

pb_ds