#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=7e5+10;
const int M=2e6+10;
#define inf 9999999999999999
struct node{ll u,v,a,l;}q[M];
struct E{ll t,nxt,w;}e[M];
ll head[N],cnt;
inline void add(ll u,ll v,ll w){
	e[++cnt]={v,head[u],w};
	head[u]=cnt; 
}
ll T,n,m;
inline void read(ll &x){
	x=0;bool f=0;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=1;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	if(f)x=-x;
}
priority_queue<pair<ll,ll>, vector<pair<ll,ll> >, greater<pair<ll, ll> > > q1;
ll vis[N],dis[M],Q;
inline void Dij(ll s){
	memset(vis,0,sizeof(vis));
	for(ll i=1;i<=n;i++)
		dis[i]=inf;
	dis[s]=0;q1.push(make_pair(0,s));
	while(!q1.empty()){
		ll x=q1.top().second;q1.pop();
		if(vis[x])continue;vis[x]=1;
		for(ll i=head[x];i;i=e[i].nxt){
			ll v=e[i].t,w=e[i].w;
			if(dis[x]+w<dis[v])
				dis[v]=dis[x]+w,
				q1.push(make_pair(dis[v],v));
		}
	}
}
bool cmp(node a,node b){return a.a>b.a;}
ll fa[N],h[N],f[N][21],tot;
inline ll find(ll x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void Ku(){
	tot=n;
	for(ll i=1;i<=n;i++)
		fa[i]=i;
	sort(q+1,q+m+1,cmp);
	for(ll i=1;i<=m;i++){
		ll u=q[i].u,v=q[i].v,a=q[i].a;
		ll fu=find(u),fv=find(v);	
		if(fu==fv)continue;
		fa[fu]=fa[fv]=++tot;
		fa[tot]=tot;h[tot]=a;
		dis[tot]=min(dis[fu],dis[fv]);
		f[fu][0]=f[fv][0]=tot;
	}

}
inline ll ask(ll v,ll p){
	for(ll i=19;~i;--i)
		if(f[v][i]&&h[f[v][i]]>p){
			v=f[v][i];
		}
    return dis[v];
}
int main(){
	read(T);
	while(T--){
		memset(head,0,sizeof(head));
		read(n);read(m);
		for(ll i=1;i<=m;i++)
			read(q[i].u),read(q[i].v),read(q[i].l),read(q[i].a),
			add(q[i].u,q[i].v,q[i].l),
			add(q[i].v,q[i].u,q[i].l);
		Dij(1);Ku();
		for(ll j=1;(1<<j)<=tot;++j)
			for(ll i=1;i<=tot;++i)
				f[i][j]=f[f[i][j-1]][j-1];
		ll last=0,k,s;
		read(Q),read(k),read(s);
		while(Q--){
			ll v,p;
			read(v);read(p);
		    v=(v+k*last-1)%n+1;
        	p=(p+1LL*k*last)%(s+1);
        	printf("%lld\n",last=ask(v,p));
		}
	}
	return 0;
}