#include<bits/stdc++.h>
#define int long long 
#define MAXM 400001
#define MAXN 200001
#define INF 1000000000000000000
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
} 
int n,m,cnt,lastans,dis[MAXN],dep[MAXN+MAXM];
int val[MAXN+MAXM],mn[MAXN+MAXM];
int dad[MAXN+MAXM][2],fa[MAXN+MAXM][25];
bool vis[MAXN];
struct path{
	int u,v,len,hig;
}p[MAXM*2];
struct node{
	int x,dis;
};
struct cmp{
	bool operator()(node a,node b){
		return a.dis>b.dis;
	}
};
bool cmp1(path a,path b){
	return a.len>b.len;
}
vector<path> e[MAXN];
vector<int> t[MAXN+MAXM];
priority_queue<node,vector<node>,cmp> q;
void Dijkstra(){
	memset(vis,0,sizeof(vis));
	for(int i=0;i<=n;i++)
	    dis[i]=INF;
	dis[1]=0;
	q.push((node){1,0});
	while(!q.empty()){
		int x=q.top().x;
		q.pop();
		if(vis[x])
		    continue;
		vis[x]=1;
		for(int i=0;i<e[x].size();i++)
		    if(dis[e[x][i].v]>dis[x]+e[x][i].len){
		    	dis[e[x][i].v]=dis[x]+e[x][i].len;
		        q.push((node){e[x][i].v,dis[e[x][i].v]});
			}
	}
}
int find(int x,int opt){
	if(dad[x][opt]==x) return x;
    return dad[x][opt]=find(dad[x][opt],opt);
}
void dfs(int x,int fat,int d){
	dep[x]=d;
	fa[x][0]=fat;
	for(int i=1;i<=24;i++)
	    fa[x][i]=fa[fa[x][i-1]][i-1];
	if(x>n)
	    mn[x]=INF;
	for(int i=0;i<t[x].size();i++)
	    if(t[x][i]!=fat){
	    	dfs(t[x][i],x,d+1);
	    	mn[x]=min(mn[x],mn[t[x][i]]);
		}     
}
signed main(){
	int T=read();
	while(T--){
		n=cnt=read(),m=read();
		lastans=0;
		memset(p,0,sizeof(p));
		memset(e,0,sizeof(e));
		memset(t,0,sizeof(t));
		memset(val,0,sizeof(val));
		memset(mn,0,sizeof(mn));
		memset(dep,0,sizeof(dep));
		memset(fa,0,sizeof(fa)); 
		memset(dad,0,sizeof(dad));
		for(int i=1;i<=m;i++){
			int u=read(),v=read(),l=read(),a=read();
			p[i].u=u,p[i].v=v,p[i].len=l,p[i].hig=a;
			p[i+m].u=v,p[i+m].v=u,p[i+m].len=l,p[i+m].hig=a;
			e[u].push_back((path){u,v,l,a});
			e[v].push_back((path){v,u,l,a});
		}
		Dijkstra();
	    for(int i=0;i<=n+m;i++)
	        dad[i][0]=dad[i][1]=i;
	    sort(p+1,p+m*2+1,cmp1);
	    int sum=0;
	    for(int i=1;i<=m*2;i++){
	    	int u=p[i].u,v=p[i].v;
	    	int dx=find(u,0),dy=find(v,0);
	    	if(dx==dy)
	    	    continue;
	    	sum++;
	    	int fx=find(u,1),fy=find(v,1);
	    	dad[dx][0]=dy;
	    	dad[fx][1]=dad[fy][1]=++cnt;
	    	t[cnt].push_back(fx),t[cnt].push_back(fy);
			t[fx].push_back(cnt),t[fy].push_back(cnt); 
			val[cnt]=p[i].hig;
			if(sum==n-1)
			    break;
		}
		for(int i=1;i<=n;i++)
		    mn[i]=dis[i];
		dfs(cnt,0,1);
		int q=read(),k=read(),s=read();
		while(q--){
			int v=read(),p=read();
			v=(v+k*lastans-1)%n+1;
			p=(p+k*lastans)%(s+1);
			for(int i=24;i>=0;i--)
			    if((dep[v]-(1<<i))>0&&val[fa[v][i]]>p)
			        v=fa[v][i];
			lastans=mn[v];
			cout<<lastans<<endl;
		}
	}
	return 0;
}