#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define N 200100
#define M 400100
#define INF 0x3f3f3f3f
using namespace std;
int head1[N],head2[N<<1],fa[N<<1][20],cnt1,cnt2,val[N<<1],ver[N<<1],vis[N],dis[N<<1];
struct Node0{
int u,v,h;
bool operator < (const Node0 &x)const{
return h>x.h;
}
}edge0[M];
struct Node1{
int to,next,w;
}edge1[M<<1];
struct Node2{
int to,next;
}edge2[N<<2];
void addEdge1(int from,int to,int w){
edge1[cnt1]=(Node1){to,head1[from],w};
head1[from]=cnt1++;
edge1[cnt1]=(Node1){from,head1[to],w};
head1[to]=cnt1++;
}
void addEdge2(int from,int to){
edge2[cnt2]=(Node2){to,head2[from]};
head2[from]=cnt2++;
edge2[cnt2]=(Node2){from,head2[to]};
head2[to]=cnt2++;
}
void init(int n){
cnt1=cnt2=0;
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head2));
memset(fa,0,sizeof(fa));
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
for(int i=1;i<=n;i++)
ver[i]=i;
}
int find(int x){
return ver[x]==x?x:(ver[x]=find(ver[x]));
}
void Dijkstra(int s){
priority_queue<pair<int,int> > Q;
Q.push(make_pair(dis[s],s));
int u,v;
while(!Q.empty()){
u=Q.top().second;
Q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head1[u];i!=-1;i=edge1[i].next){
v=edge1[i].to;
if(dis[v]>dis[u]+edge1[i].w){
dis[v]=dis[u]+edge1[i].w;
Q.push(make_pair(-dis[v],v));
}
}
}
}
void kruskal(int n,int m){
int num=n,x,y;
for(int i=0;i<m;i++){
x=find(edge0[i].u);
y=find(edge0[i].v);
if(x!=y){
num++;
ver[x]=ver[y]=num;
val[num]=edge0[i].h;
addEdge2(x,num);
addEdge2(y,num);
if(num - n == n-1) return;
}
}
}
void dfs(int u,int fath){
fa[u][0]=fath;
for(int i=1;i<=19;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head2[u];i!=-1;i=edge2[i].next){
int v=edge2[i].to;
if(v!=fath){
dfs(v,u);
dis[u]=min(dis[u],dis[v]);
}
}
}
int lca(int x,int h){
for(int i=19;i>=0;i--){
if(fa[x][i] && val[fa[x][i]]>h)
x=fa[x][i];
}
return dis[x];
}
int main(){
int T,n,m,u,v,l,h,Q,K,S,v0,p0,p,lastans=0;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
init(2*n);
for(int i=0;i<m;i++){
scanf("%d%d%d%d",&u,&v,&l,&h);
edge0[i].u=u,edge0[i].v=v,edge0[i].h=h;
addEdge1(u,v,l);
}
Dijkstra(1);
sort(edge0,edge0+m);
kruskal(n,m);
dfs(2*n-1,0);
scanf("%d%d%d",&Q,&K,&S);
while(Q--){
scanf("%d%d",&v0,&p0);
v=(v0+K*lastans-1)%n+1;
p=(p0+K*lastans)%(S+1);
lastans=lca(v,p);
printf("%d\n",lastans);
}
}
return 0;
}