#include <bits/stdc++.h>
#define R(x) x = read()
#define ENDL push('\n');
#define SPACE push(' ');
#define int long long
#define mp make_pair
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
	if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
	*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	if (x<0)x=-x,push('-');
	int sta[35],top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while (x);
	while(top)push(sta[--top]^'0');
}
#ifdef LOCAL
	inline int read() {
		int r=0,f=1;
		char c=getchar();
		while(c>'9'||c<'0') {
			if(c=='-')f=0;
			c=getchar();
		}
		while(c>='0'&&c<='9')r=(r<<3)+(r<<1)+(c^'0'),c=getchar();
		return f?r:(-r);
	}
#else
	char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
	inline int read() {
	    int x=0,f=1;char ch=getchar();
	    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	    return x*f;
	}
#endif
int t,n,m,Q,k,s;
struct b{
	int u,v,l,a;
}e[800100];
struct edge{
	int to,nxt,l,a;
}v[1600100];
int len,fir[800100];
int a[800100];
void add(int x,int y,int l,int a){
	++len;
	v[len].to=y;
	v[len].nxt=fir[x];
	v[len].l=l;
	v[len].a=a;
	fir[x]=len;
}
int f[800100];
int find(int x){
	while(x^f[x])x=f[x]=f[f[x]];
	return x;
}
int mrg(int x,int y){
	x=find(x);
	y=find(y);
	if(x==y)return 0;
	f[x]=y;
	return 1;
}
int dis[800100],vis[800100];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int lans,cnt;
int mi[800100],fa[800100][30];
void dfs(int u,int f){
	mi[u]=dis[u];
	for(int i=fir[u];i;i=v[i].nxt){
		if(v[i].to==f)continue;
		fa[v[i].to][0]=u;
		dfs(v[i].to,u);
		mi[u]=min(mi[u],mi[v[i].to]);
	}
}

void dij(){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f3f3f3f,sizeof(dis));
	int s=1;
	dis[1]=0;
	q.push(mp(0,1));
	while(!q.empty()){
		int s=q.top().second;
		q.pop();
		if(vis[s])continue;
		vis[s]=1;
		for(int i=fir[s];i;i=v[i].nxt){
			if(dis[v[i].to]>dis[s]+v[i].l){
				dis[v[i].to]=dis[s]+v[i].l;
				q.push(mp(dis[v[i].to],v[i].to));
			}
		}
	}
}
signed main(){
	freopen("return5.in","r",stdin);
	freopen("return3.out","w",stdout);
	R(t);
	while(t--){
		len=lans=0;
		memset(fir,0,sizeof(fir));
		R(cnt=n);R(m);
		for(int i=1;i<=m;i++){
			R(e[i].u);
			R(e[i].v);
			R(e[i].l);
			R(e[i].a);
			add(e[i].u,e[i].v,e[i].l,e[i].a);
			add(e[i].v,e[i].u,e[i].l,e[i].a);
		}
		dij();
		len=0;
		memset(fir,0,sizeof(fir));
		sort(e+1,e+1+n,[](b x,b y){
			return x.a>y.a;
		});
		for(int i=1;i<=n+n;i++)f[i]=i;
		for(int i=1;i<=m;i++){
			if(find(e[i].v)^find(e[i].u)){
				a[++cnt]=e[i].a;
				add(cnt,find(e[i].v),0,e[i].a);
				add(cnt,find(e[i].u),0,e[i].a);
				add(find(e[i].v),cnt,0,e[i].a);
				add(find(e[i].u),cnt,0,e[i].a);
				mrg(e[i].u,cnt);
				mrg(e[i].v,cnt);
			}
		}
		dfs(cnt,0);
		for(int j=1;j<=25;j++){
			for(int i=1;i<=cnt;i++){
				fa[i][j]=fa[fa[i][j-1]][j-1];
			}
		}
		R(Q);R(k);R(s);
		while(Q--){
			int v0,p0;
			R(v0);R(p0);
			v0=(v0+lans*k-1)%n+1;
			p0=(p0+lans*k)%(s+1);
			for(int i=25;i>=0;i--){
				if(fa[v0][i]&&a[fa[v0][i]]>p0){
					v0=fa[v0][i];
				}
			}
			lans=mi[v0];
			write(lans);
			ENDL
		}
	}
    return 0;
}