#include<bits/stdc++.h> using namespace std; const int N=2e6; int node[N],nxt[N],head[N],data[N]; int n,m,d[N],tot,begins; int abs(int x) { if(x<0) return -x; else return x; } void add(int x,int y,int z){ node[++tot]=y;nxt[tot]=head[x];head[x]=tot;data[tot]=z; } struct ss { int x,y; }s[10022]; void Dij(){ memset(d,10,sizeof d);d[begins]=0; priority_queue<pair<int,int> > heap; heap.push(make_pair(-d[begins],begins)); while (1){ for (;!heap.empty() && -d[heap.top().second]!=heap.top().first;heap.pop()); if (heap.empty()) break; int now=heap.top().second; heap.pop(); for (int i=head[now];i;i=nxt[i]){ int j=node[i]; if (d[j]>d[now]+data[i]){ d[j]=d[now]+data[i]; heap.push(make_pair(-d[j],j)); } } } }