用 Kruskal 重构树 写的

#include<bits/stdc++.h>
using namespace std;
#define re register
const int N=5e5+100;long long inf=10e9;
int P[23];
int n,m,fa[N],val[N],nod;long long mi[N]; 
int de[N],anc[N][21];
struct edge{int x,y,z;}e[N];
bool cmp(edge A,edge B){return A.z>B.z;}
int head[N],to[N],ne[N],tot;
void add(int x,int y){
	ne[++tot]=head[x];
	to[tot]=y;
	head[x]=tot;
	return;
}
struct Dij{
	bool vis[N]; long long dis[N];
	struct node{
		long long id,dis;
		bool operator <(node it) const{return dis>it.dis;}
	};priority_queue<node>q;
	int head[N],to[N],w[N],ne[N],tot;
	void deal(){
		for(re int i=1;i<=n;i++) head[i]=0,vis[i]=0;
		tot=0;
		return;
	}
	void add(int x,int y,int z){
		ne[++tot]=head[x];
		to[tot]=y,w[tot]=z;
		head[x]=tot;
		return;
	}
	void dij(){
		for(re int i=1;i<=n;i++) dis[i]=inf;
		dis[1]=0;
		q.push((node){1,dis[0]});
		while(!q.empty()){
			node u=q.top(); q.pop();
			if(vis[u.id]) continue;
			vis[u.id]=1;
			for(int i=head[u.id];i;i=ne[i]){
				int v=to[i];
				if(dis[v]>u.dis+w[i])
					dis[v]=u.dis+w[i],q.push((node){v,dis[v]});
			}
		}
		return;
	}
}D;
void pre_dfs(int u,int f){
//	cout<<u<<endl;
	if(u<=n) mi[u]=D.dis[u];
	else mi[u]=inf;
	de[u]=de[f]+1,anc[u][0]=f;
	for(re int i=1;i<=19;i++) anc[u][i]=anc[anc[u][i-1]][i-1];
	for(re int i=head[u];i;i=ne[i]){
		int v=to[i];
		pre_dfs(v,u);
		mi[u]=min(mi[u],mi[v]);
	}
	return;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void krual_tree(){
	sort(e+1,e+1+m,cmp);
	for(re int i=1;i<=m;i++){
		int x=e[i].x,y=e[i].y,z=e[i].z;
		int fx=find(x),fy=find(y);
		if(fx==fy) continue;
		nod++,val[nod]=z;
		fa[fx]=fa[fy]=nod;
		add(nod,fx),add(nod,fy);
	}
	return;
}
int check(int x,int mid,int p){
	for(re int i=19;i>=0;i--){
		if(P[i]<=mid) mid-=P[i],x=anc[x][i];
		if(val[x]<p) return -1; 
	}
	return x;
}
void deal(){
	nod=0,tot=0;
	memset(fa,0,sizeof(fa));
	memset(head,0,sizeof(head));
	memset(val,0,sizeof(val));
	memset(anc,0,sizeof(anc));
	return;
}
int main(){
	P[0]=1;
	for(re int i=1;i<=19;i++) P[i]=P[i-1]*2;
	int T; cin>>T;
	while(T--){
		cin>>n>>m; nod=n;
		for(re int i=1;i<=2*n;i++) fa[i]=i;
		for(re int i=1;i<=m;i++){
			int u,v,l,a;
			scanf("%d%d%d%d",&u,&v,&l,&a);
			e[i]=(edge){u,v,a};
			D.add(u,v,l),D.add(v,u,l);
		}
		D.dij(),krual_tree(),pre_dfs(nod,0);
		int Q,K,S;
		cin>>Q>>K>>S;
		long long ans=0;
		for(re int i=1;i<=Q;i++){
			long long v0,p0;
			scanf("%lld%lld",&v0,&p0);
			v0=(v0+K*ans-1)%n+1,p0=(p0+K*ans)%(S+1);
			int v=v0,p=p0,lca=v;
			for(int i=19;i>=0;i--) if(P[i]<=de[lca]-1 and val[anc[lca][i]]>p) lca=anc[lca][i];
			ans=mi[lca];
			cout<<ans<<endl;
		}
		deal(),D.deal();
	}
}