#include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 #define rg register

 #define N 400010

 using namespace std;

 int T,n,m,q,k,s,tot,cnt,last[N],f[N],pos[N],p[N][],hei[N];

 LL ans,mn[N];

 struct edge{

     int to,pre,dis;

 }e[N<<];

 struct rec{

     int u,v,h;

 }r[N<<];

 struct heap{

     LL d;int p;

 }h[N];

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=='-'&&(f=-),c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 inline void up(int x){

     int fa;

     while((fa=(x>>))&&h[fa].d>h[x].d) swap(h[x],h[fa]),swap(pos[h[x].p],pos[h[fa].p]),x=fa;

 }

 inline void down(int x){

     int son;

     while((son=(x<<))<=tot){

         if(son<tot&&h[son].d>h[son+].d) son++;

         if(h[son].d<h[x].d) swap(h[x],h[son]),swap(pos[h[x].p],pos[h[son].p]),x=son;

         else return;

     }

 }

 inline void dijkstra(int x){

     for(rg int i=;i<=(n<<);i++) mn[i]=4e9;

     h[tot=pos[x]=]=(heap){mn[x]=,x};

     while(tot){

         int now=h[].p; pos[h[tot].p]=; h[]=h[tot--]; if(tot) down();

         for(rg int i=last[now],to;i;i=e[i].pre)

         if(mn[to=e[i].to]>mn[now]+e[i].dis){

             mn[to]=mn[now]+e[i].dis;

             if(!pos[to]) h[pos[to]=++tot]=(heap){mn[to],to};

             else h[pos[to]].d=mn[to];

             up(pos[to]);

         }

     }

 }

 inline int climb(int x,int y){

     for(rg int i=;i>=;i--) if(hei[p[x][i]]>y) x=p[x][i]; return x;

 }

 int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

 inline bool cmp(rec a,rec b){return a.h>b.h;}

 inline void Pre(){

     tot=; cnt=; ans=;

     memset(last,,sizeof(last));

     memset(pos,,sizeof(pos));

     memset(p,,sizeof(p));

 }

 int main(){

     freopen("return.in","r",stdin);

     freopen("return.out","w",stdout);

     T=read();

     while(T--){

         Pre();

         n=read(); m=read();

         for(rg int i=;i<=m;i++){

             int u,v,d;

             r[i].u=u=read(),r[i].v=v=read(),d=read(),r[i].h=read();

             e[++tot]=(edge){v,last[u],d}; last[u]=tot;

             e[++tot]=(edge){u,last[v],d}; last[v]=tot;

         }

         dijkstra();

     //    for(rg int i=1;i<=n;i++) printf("%d ",mn[i]); puts("mn");

         tot=n;

         sort(r+,r++m,cmp);

         for(rg int i=;i<=n;i++) f[i]=i,f[i+n]=i+n;

         for(rg int i=;i<=m;i++){

             int u=find(r[i].u),v=find(r[i].v);

             if(u!=v){

                 hei[++tot]=r[i].h; mn[tot]=min(mn[u],mn[v]);

                 f[u]=f[v]=p[u][]=p[v][]=tot;

                 cnt++;

             }

             if(cnt==n-) break;

         }

         for(rg int j=;j<;j++)

             for(rg int i=;i<=tot;i++) p[i][j]=p[p[i][j-]][j-];

         q=read(); k=read(); s=read();

         while(q--){

             int v0=(read()+k*ans-)%n+,p0=(read()+k*ans)%(s+);

     //        printf("v0=%d p0=%d\n",v0,p0);

             printf("%lld\n",ans=mn[climb(v0,p0)]);

         }

     }

     return ;

 }