#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+5;
struct pii{
	int s,x;
};
struct edge{
	int u,v,h;
}e[maxn*2];
bool operator<(pii a,pii b){
	return a.s>b.s;
}
int dis[maxn],i,head[maxn],nxt[maxn*4],to[maxn*4],t,k,wei[maxn],ans;
int n,m,u,v,h,l,vis[maxn],f[maxn],fa[25][maxn],fac[25][maxn],qq,s,p;
priority_queue<pii> q;
inline bool cmp(edge a,edge b){
	return a.h>b.h;
}
inline void add(int u,int v,int l){
	nxt[++k]=head[u];
	head[u]=k;
	to[k]=v;
	wei[k]=l;
}
inline void Dijkstra(){
	q.push((pii){0,1});
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[1]=0;
	while(!q.empty()){
		pii t=q.top();
		q.pop();
		if(vis[t.x]==1) continue;
		vis[t.x]=1;
		for(int j=head[t.x];j!=0;j=nxt[j])
		if(dis[to[j]]>dis[t.x]+wei[j]){
			dis[to[j]]=dis[t.x]+wei[j];
			q.push((pii){dis[to[j]],to[j]});
		}
	}
}
inline int find(int x){
	if(f[x]==0) return x;
	else return f[x]=find(f[x]);
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		memset(f,0,sizeof(f));
		k=0;
		memset(head,0,sizeof(head));
		for(i=1;i<=m;i++){
			scanf("%d%d%d%d",&u,&v,&l,&h);
			add(u,v,l);
			add(v,u,l);
			e[i]=(edge){u,v,h};
		}
		Dijkstra();
		sort(e+1,e+1+m,cmp);
		int cnt=0;
		for(i=1;i<=m;i++){
			int x=find(e[i].u),y=find(e[i].v);
			if(x!=y)
			if(dis[x]<dis[y]){
				f[y]=x;
				fa[0][y]=x;
				fac[0][y]=e[i].h;
				cnt++;
			} else {
				f[x]=y;
				fa[0][x]=y;
				fac[0][x]=e[i].h;
				cnt++;
			}
			if(cnt>=n-1) break;
		}
		for(i=1;i<=20;i++)
		for(int j=1;j<=n;j++){
			fa[i][j]=fa[i-1][fa[i-1][j]];
			fac[i][j]=min(fac[i-1][j],fac[i-1][fa[i-1][j]]);
		}
		scanf("%d%d%d",&qq,&k,&s);
		ans=0;
		while(qq--){
			scanf("%d%d",&v,&p);
			v=(v+k*ans-1)%n+1;
			p=(p+k*ans)%(s+1);
			i=0;
			while(fa[i][v]!=0&&fac[i][v]>p) i++;
			for(i--;i>=0;i--) if(fa[i][v]!=0&&fac[i][v]>p) v=fa[i][v];
			ans=dis[v];
			printf("%d\n",ans);
		}
	}
	return 0;
}