struct yxQueue{
	int a[524288];
	int cnt1=0;
	void up(int v)
	{
		while(v!=1&&a[v]<a[v/=2])
		{
			swap(a[v],a[v/=2]);
			v/=2;
		}
	}
	void down(int v)
	{
		while(v*2<=cnt1)
		{
			int t;
			t=v*2;
			if(t<cnt1&&a[t+1]<a[t]) t++;
			if(a[v]<a[t]) break;
			swap(a[v],a[t]);
			v=t;
		}
	}
	void push(int x)
	{
		a[++cnt1]=x;
		up(cnt);		
	}
	void pop()
	{
		swap(a[cnt1],a[1]);
		cnt1--;
		down(1);
	}
	bool empty(){return cnt1==0;}
	int front(){return a[1];}	
}q;
void add(int u,int v,int w1)
{
	nxt[++cnt]=hd[u];
	hd[u]=cnt;
	to[cnt]=v;
	w[cnt]=w1;
}
void dij(int x)
{
	for(int i=1;i<=n;i++) dis[i]=0x7f7f7f7f7f,vis[i]=0,cs[i]=0;
	dis[x]=0;
//	q.cnt1=0;
	q.push(x);
	int u;
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		if(vis[u]!=0) continue;
		vis[u]=1;
		for(int i=hd[u];i;i=nxt[i])
		{
			if(dis[to[i]]>dis[u]+w[i])
			{
				dis[to[i]]=dis[u]+w[i];
				q.push(to[i]);
//				cout<<q.cnt1<<endl;
			}
		}
	}
}