#include<bits/stdc++.h>
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
struct edge { int v,w,a,nxt; }e[800010];
int cnt=1,dis[200010],n,m,hd[200010];
bool vis[200010];
inline int read ( void )
{
int x=0;char ch=getchar();
while ( !isdigit(ch) ) ch=getchar();
while ( isdigit(ch) ) x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x;
}
inline void print ( int x )
{
if ( !x ) { puts("0");return; }
int s[12],tp=0;clr(s);
while ( x ) s[++tp]=x%10,x/=10;
while ( tp ) putchar(s[tp--]+48);
putchar('\n');
}
inline void addedge ( int u,int v,int w,int a )
{
e[++cnt].v=v;e[cnt].w=w;e[cnt].a=a;e[cnt].nxt=hd[u];hd[u]=cnt;
e[++cnt].v=u;e[cnt].w=w;e[cnt].a=a;e[cnt].nxt=hd[v];hd[v]=cnt;
}
inline void spfa ( int s )
{
memset(dis,127,sizeof(dis));clr(vis);
dis[s]=0;vis[s]=true;queue<int> q;q.push(s);
while ( !q.empty() )
{
int now=q.front();q.pop();vis[now]=false;
for ( int i=hd[now];i;i=e[i].nxt )
if ( dis[e[i].v]>dis[now]+e[i].w )
{
dis[e[i].v]=dis[now]+e[i].w;
if ( !vis[e[i].v] ) q.push(e[i].v),vis[e[i].v]=true;
}
}
}
int tmp[2000],sum[2000],lth[2000];
inline void ycl2 ( void )
{
for ( int i=2;i<=n;i++ ) sum[i]=sum[i-1]+lth[i-1];
}
inline int work2 ( int v,int p )
{
while ( v!=1 )
{
if ( tmp[v-1]<=p ) return sum[v];
v--;
}
return 0;
}
int main()
{
int T=read();
while ( T-- )
{
clr(hd);clr(e);cnt=1;
n=read();m=read();
bool f1=true,f2=(m==n-1);
for ( int i=1,u,v,w,a;i<=m;i++ )
{
u=read(),v=read(),w=read(),a=read(),addedge(u,v,w,a);
f1&=(a==1),f2&=(u+1==v);tmp[u]=a;lth[u]=w;
}
if ( f2 ) ycl2();
else spfa(1);
int Q=read(),K=read(),S=read(),ls=0;
while ( Q-- )
{
int vv=(read()+K*ls-1)%n+1,pp=(read()+K*ls)%(S+1);
if ( f1 ) ls=pp?dis[vv]:0;
else if ( f2 ) ls=work2(vv,pp);
printf("%d\n",ls);
}
}
return 0;
}