样例五1.3s。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll T;
ll n,m;
ll tt,nt[N<<1],hd[N],to[N<<1],wt[N<<1],dis[N],vis[N];
//******************************
void push(ll u,ll v,ll w){
	to[++tt]=v;nt[tt]=hd[u];hd[u]=tt;wt[tt]=w;
}
struct node{
	ll fst,sec;
	bool operator<(const node &x) const{
		return x.fst<fst;
	}
};
priority_queue<node> q;
void dijkstra(){
	q.push(node{0,1});
	while(!q.empty()){
		ll d=q.top().fst,x=q.top().sec;
		q.pop();
		if(vis[x])	continue;
		vis[x]=1;
		for(int i=hd[x];i;i=nt[i]){
			ll y=to[i],w=wt[i];
			if(d+w<dis[y]){
				dis[y]=d+w;
				if(!vis[y])	q.push(node{dis[y],y});
			}
		}
	}
}
//******************************最短路 
struct edge{
	ll u,v,de;
}e[N<<1];
bool cmp(const edge &a1,const edge &a2){
	return a1.de>a2.de;
}
ll fa[N],et;
ll get(ll nw){
	if(fa[nw]==nw){
		return nw;
	}
	fa[nw]=get(fa[nw]);
	return fa[nw];
}
void merge(ll x,ll y){
	fa[get(x)]=get(y);
}
//******************************最小生成树
ll cnt,rt[N<<1],sz[N<<1],ans[N<<1];
ll kf[22][N<<1];
void init(){
	cnt=n;
	for(int i=1;i<=n*2;i++){
		rt[i]=i;
		ans[i]=dis[i];
		sz[i]=1e18;
	}
}
ll getrt(ll nw){
	if(rt[nw]==nw)	return nw;
	rt[nw]=getrt(rt[nw]);
	return rt[nw];
}
void merging(ll x,ll y,ll l){
	merge(x,y);
	ll rx=getrt(x),ry=getrt(y);
	cnt++;
	kf[0][rx]=kf[0][ry]=cnt;
	sz[cnt]=l;
	ans[cnt]=min(ans[rx],ans[ry]);
	rt[rx]=rt[ry]=cnt;
}
void kruskal_rebuild(){
	for(int i=1;i<=20;i++){
		for(int j=1;j<=cnt;j++){
			kf[i][j]=kf[i-1][kf[i-1][j]];
		}
	}
}
//******************************克鲁斯卡尔重构树 
void clean(){
	memset(nt,0,sizeof(nt));
	memset(e,0,sizeof(e));
	memset(hd,0,sizeof(hd));
	memset(to,0,sizeof(to));
	memset(wt,0,sizeof(wt));
	memset(vis,0,sizeof(vis));
	memset(kf,0,sizeof(kf));
	memset(ans,0,sizeof(ans));
	memset(rt,0,sizeof(rt));
	memset(sz,0,sizeof(sz));
	tt=et=dis[1]=cnt=0;
	for(int i=2;i<N;i++){
		dis[i]=1e18;
	}
	for(int i=1;i<N;i++){
		fa[i]=i;
	}
}
//******************************初始化
inline ll read(){
	ll a=0;
	char c=getchar();
	while(c<'0'||c>'9')	c=getchar();
	while(c<='9'&&c>='0'){
		a=a*10+(c-'0');
		c=getchar();
	}
	return a;
} 
//******************************快读 
void solve(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=m;i++){
		ll u,v,w,l;
		u=read();v=read();w=read();l=read();
		push(u,v,w);push(v,u,w);
		e[++et]={u,v,l};
	}
	dijkstra();
	sort(e+1,e+et+1,cmp);
	init();
	for(int i=1,j=0;i<=et;i++){
		if(get(e[i].u)==get(e[i].v))	continue;
		merging(e[i].u,e[i].v,e[i].de);
		j++;
		if(j==n-1)	break;
	}
	kruskal_rebuild();
	ll Q,K,S,lastans=0;
	scanf("%lld %lld %lld",&Q,&K,&S);
	while(Q--){
		ll v,p;
		scanf("%lld %lld",&v,&p);
		v=(v+K*lastans-1)%n+1;
		p=(p+K*lastans)%(S+1);
		ll nw=v;
		for(int i=20;i>=0;i--){
			if(nw==cnt)	break;
			if(sz[kf[i][nw]]>p)	nw=kf[i][nw];
		}
		lastans=ans[nw];
		printf("%lld\n",lastans);
	}
}

signed main(){
	scanf("%lld",&T);
	while(T--){
		clean();
		solve();
	}
}
/*simple
1
5 5
1 2 1 2
2 3 1 4
4 3 1 1
5 3 1 3
1 5 2 5
4 1 3
5 1
5 2
2 0
4 0
*/