#include<bits/stdc++.h>
using namespace std;
#define int long long

struct node{
	int from,to,next,val,high,id;
}e[2000001],tree[2000001];

int head[2000001],cnt;
int head2[2000001],cnt2;

void add(int uu,int vv,int ww,int aa){
	e[++cnt].to=vv;
	e[cnt].from=uu;
	e[cnt].val=ww;
	e[cnt].id=cnt;
	e[cnt].high=aa;
	e[cnt].next=head[uu];
	head[uu]=cnt;
}

void add2(int uu,int vv,int ww,int aa){
	tree[++cnt2].to=vv;
	tree[cnt2].from=uu;
	tree[cnt2].val=ww;
	tree[cnt2].high=aa;
	tree[cnt2].next=head2[uu];
	head2[uu]=cnt2;
}

struct ne{
    int v;
    int id;
    ne(int aaa,int bbb):v(aaa),id(bbb){}
    bool operator<(const ne &x)const{
        return x.v<v;
    }
};

int qq,kk,ss;
int n,m,b,dis[2000001],vis[2000001];
priority_queue<ne> mx;

void dijkstra(int s){
	memset(dis,0x7f7f7f7f7f7f7f7f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	mx.push({0,s});
	while(!mx.empty()){
		int headid=mx.top().id,headv=mx.top().v;mx.pop();
		if(vis[headid])continue;
		vis[headid]=1;
		for(int i=head[headid];i;i=e[i].next){
		    int q=e[i].to;
		    if(headv+e[i].val<dis[q]){
		    	dis[q]=dis[headid]+e[i].val;
		    	mx.push({dis[q],q});
			}
		}
    }
}

bool cmp(node x,node y){
	if(x.high==y.high){
	   return x.id<y.id;
	}
//	else 
	else return x.high>y.high;
}

int rebuild,fa[2000001],worth[2000001],mn[2000001];

int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}

void dfs(int x,int fa){
	//cout<<x<<"->";
	//cout<<"(("<<x<<"))"<<endl;
	if(x<=n)mn[x]=dis[x];
	else mn[x]=0x7f7f7f7f7f7f7f7f;
	for(int i=head2[x];i;i=tree[i].next){
		int v=tree[i].to;
		if(v==fa)continue;
		dfs(v,x);
		mn[x]=min(mn[x],mn[v]);
	}
}

int st[2000001][26];

signed main(){
// 	freopen("return.in","r",stdin);
// 	freopen("return.out","w",stdout);
	int T=0;
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		b=1;cnt=cnt2=0;
		memset(head,0,sizeof(head));
		memset(head2,0,sizeof(head2));
		for(int i=1;i<=m;i++){
			int xu,xv,xw,xh;
			cin>>xu>>xv>>xw>>xh;
			add(xu,xv,xw,xh);
			add(xv,xu,xw,xh);
		//	cout<<cnt<<endl;
		}
		dijkstra(b);
		sort(e+1,e+2*cnt+1,cmp);
//		for(int i=1;i<=cnt;i++){
//			cout<<e[i].from<<" "<<e[i].to<<endl;
//		}
		for(int i=1;i<=2*n;i++){
			fa[i]=i;
		}
		rebuild=n;
		for(int i=1;(i<=2*cnt)&&(rebuild<2*n);i+=2){
			int u=e[i].from,v=e[i].to;
		//	cout<<"==="<<u<<" "<<v<<endl;
			int fu=find(u),fv=find(v);
			if(fu==fv){
				//cout<<"+"<<endl;
				continue;
			}
			++rebuild;
			st[fv][0]=rebuild;
			st[fu][0]=rebuild;
			add2(fu,rebuild,0,0);
			add2(rebuild,fu,0,0);
			add2(fv,rebuild,0,0);
			add2(rebuild,fv,0,0);
			fa[fu]=rebuild;
			fa[fv]=rebuild;
			worth[rebuild]=e[i].high;
			//cout<<e[i].high<<endl;
			//cout<<"->"<<i<<" "<<rebuild<<endl;
		}
		//cout<<"ys1:"<<2*n<<endl;
		cin>>qq>>kk>>ss;
		//cout<<"imp:"<<rebuild<<endl;
		dfs(rebuild,0);
		for(int l=1;l<=20;l++){
			for(int j=1;j<=rebuild;j++){
				st[j][l]=st[st[j][l-1]][l-1];
			}
		}
//		for(int i=1;i<2*n;i++){
//			cout<<"+"<<st[i][0]<<endl;
//		}
		int v0,p0,ans=0;
		for(int i=1;i<=qq;i++){
			cin>>v0>>p0;
//			if(i==1){
//				ans=0;
//				cout<<ans<<endl;
//				continue;
//			}
			int vp,pp;
			vp=(v0+kk*ans-1)%n+1;
			pp=(p0+kk*ans)%(ss+1);
			//cout<<vp<<" "<<pp<<endl;
			for(int j=20;j>=0;j--){
				if(worth[st[vp][j]]>pp&&st[vp][j]!=0)vp=st[vp][j];
			}
			ans=mn[vp];
			cout<<ans<<endl;
		}
	}
	return 0;
}