#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<utility>
#include<vector>
#include<queue>
#include<bitset>
#include<map>
#include<set>
#define FOR(i,a,b) for(register int i=a;i<=b;++i)
#define ROF(i,a,b) for(register int i=a;i>=b;--i)
#define mp(a,b) make_pair(a,b)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define fi first
#define se second
#define eb emplace_back
#define ep emplace
using namespace std;
inline int read();
typedef long long ll;
typedef double db;
const int N=4e5+5;
const int M=6e5+5;
const int inf=0x3f3f3f3f;
const int INF=0x7f7f7f7f;
int n,m,k;
void init();
struct E{
	int to,nex,w;
}edge[M<<1];int head[N],cnt=0;
void add(int u,int v,int w){
	edge[++cnt]={v,head[u],w};
	head[u]=cnt;
}
struct E_{
	int u,v,l,a;
}Edge[M];
struct node{
	int dis,pos;
	bool operator <(const node &x)const{
		return dis>x.dis;
	}
};
priority_queue<node>q;
int dist[N];bitset<N>vis;
void dij(){
	memset(dist,0x7f,sizeof dist);
//	FOR(i,1,n) dist[i]=INF;
	q.push({0,1});dist[1]=0;vis.reset();
	while(!q.empty()){
		int u=q.top().pos;q.pop();
		if(vis[u]) continue;vis[u]=1;
		for(int i=head[u];i;i=edge[i].nex){
			int v=edge[i].to,w=edge[i].w;
			if(!vis[v]&&dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				q.push({dist[v],v});
			}
		}
	}
}
int f[N<<1],tot=0,val[N<<1];
struct _E{int to,nex;}e[M<<2];int h[N<<1],cnnt=0;
void Add(int u,int v){e[++cnnt]={v,h[u]};h[u]=cnnt;}
bool cmp1(E_ x,E_ y){return x.a>y.a;}
int Get(int k){return f[k]==k?k:f[k]=Get(f[k]);}
void krus(){
	sort(Edge+1,Edge+1+m,cmp1);
	FOR(i,1,m){
		int u=Edge[i].u,v=Edge[i].v,w=Edge[i].a;
		int fu=Get(u),fv=Get(v);
		if(fu==fv) continue;
		tot++;
		f[tot]=tot;val[tot]=w;
		f[fu]=tot;f[fv]=tot;
		Add(tot,fu);Add(fu,tot);
		Add(tot,fv);Add(fv,tot);
	}
}
int V[N<<1],F[N<<1][30],dep[N<<1];
void dfs(int u,int fa){
	for(int i=1;1<<i<=dep[u];i++) F[u][i]=F[F[u][i-1]][i-1];
	if(u<=n) {V[u]=dist[u];return ;}
	else V[u]=INF;
	for(int i=h[u];i;i=e[i].nex){
		int v=e[i].to;
		if(v==fa) continue;
		F[v][0]=u;
		dep[v]=dep[u]+1;
		dfs(v,u);
		V[u]=min(V[u],V[v]);
	}
}
void LHLeisus(){
	n=read(),m=read();tot=n;
	FOR(i,1,n) f[i]=i;
	FOR(i,1,m){
		int u=read(),v=read(),l=read(),a=read();
		Edge[i]={u,v,l,a};
		add(u,v,l);
		add(v,u,l);
	}
	dij();
	krus();dep[tot]=1;
	dfs(tot,0);
	int Q=read(),K=read(),S=read();
	int lastans=0;
	while(Q--){
		int v=read(),p=read();
		v=(v+K*lastans-1)%n+1;
		p=(p+K*lastans)%(S+1);
		for(int i=30;i>=0;i--){
			if(F[v][i]&&val[F[v][i]]>p){
				v=F[v][i];
			}
		}
		lastans=V[v];
		printf("%d\n",lastans);
	}
}
int main()
{
//	freopen("return5.in","r",stdin);
//	freopen("return5.out","w",stdout);
//	if(system("fc return5.ans return5.out")) puts("");
//	return 0;
	int T=read();
	while(T--){
		init();
		LHLeisus();
	}
	return 0;
	//あまりに短い夏だけで何を残していけるのかな？
}
void init(){
	memset(head,0,sizeof head);cnt=0;
	while(!q.empty()) q.pop();
	memset(h,0,sizeof h);cnnt=0;
	memset(f,0,sizeof f);
	memset(val,0,sizeof val);
	memset(F,0,sizeof F);
	memset(V,0x7f,sizeof V);
	memset(dep,0,sizeof dep);
}

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f*x;
}