大样例4和5不能通过

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct edge{
	int to,v;
	bool operator<(const edge b)const{
		return v<b.v;
	}
	bool operator>(const edge b)const{
		return v>b.v;
	}
};
struct edge2{
	int a,b,h;
}e2[400010];
int t,n,m,u,v,w,h;
int q,k,s,cst,cwh,st,wh;
int nxt,ans;
int dis[800010],val[800010];
int rt[800010],dep[800010],fa[800010][31];
bool f[200010];
vector<edge> e[800010];
vector<int> tr[800010];
int findr(int now){
	if(rt[now]!=now) rt[now]=findr(rt[now]);
	return rt[now];
}
bool cmp(edge2 a,edge2 b){
	return a.h>b.h;
}
void dijk(){
	int now,ndis,to,tv;
	priority_queue<edge,vector<edge>,greater<edge> > que;
	que.push({1,0}),dis[1]=0;
	while(!que.empty()){
		now=que.top().to,ndis=que.top().v;
		que.pop();
		if(f[now]) continue;
		f[now]=1;
		if(e[now].empty()) continue;
		for(int i=0;i<e[now].size();i++){
			to=e[now][i].to,tv=e[now][i].v;
			if(f[to]) continue;
			if(dis[to]>(dis[now]+tv)){
				dis[to]=dis[now]+tv;
				que.push({to,dis[to]});
			}
		}
	}
	return;
}
void krus(){
	int num=0,af,bf;
	sort(e2+1,e2+m+1,cmp);
	for(int i=1;i<=m;i++){
		af=findr(e2[i].a),bf=findr(e2[i].b);
		if(af==bf) continue;
		rt[af]=rt[bf]=(++nxt);
		tr[af].push_back(nxt),tr[nxt].push_back(af);
		tr[bf].push_back(nxt),tr[nxt].push_back(bf);
		val[nxt]=min(e2[i].h,min(val[af],val[bf]));
		if((++num)==n-1) break;
	}
	return;
}
void dfs(int now,int ff){
	//cout<<now;
	dep[now]=dep[ff]+1,fa[now][0]=ff;
	for(int i=1;i<=30;i++) fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=0;i<tr[now].size();i++){
		if(tr[now][i]==ff) continue;
		dfs(tr[now][i],now);
		dis[now]=min(dis[now],dis[tr[now][i]]);
	}
	return;
}
int fans(int now){
	for(int i=30;i>=0;i--){
		if(dep[now]>(1<<i)&&val[fa[now][i]]>wh) now=fa[now][i];
	}
	//cout<<now<<'-'<<endl;
	return dis[now];
}
void work(){
	cin>>n>>m,nxt=n; 
	for(int i=1;i<=n*4;i++){
		e[i].clear(),tr[i].clear();
		dis[i]=val[i]=1e7,f[i]=0,rt[i]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w>>h;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
		e2[i]={u,v,h};
	}
	dijk(),krus(),dfs(nxt,0);
	cin>>q>>k>>s;
	for(int i=1;i<=q;i++){
		cin>>cst>>cwh;
		st=(cst+ans*k-1)%n+1;
		wh=(cwh+ans*k)%(s+1);
		ans=fans(st);
		cout<<ans<<endl;
	}
	return;
}
int main(){
	//freopen("return5.in","r",stdin);
	//freopen("a.out","w",stdout);
	cin>>t;
	while(t--) ans=0,work();
	return 0;
}