//minamoto

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cstdio>

 #include<queue>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char sr[<<],z[];int C=-,Z;

 inline void Ot(){fwrite(sr,,C+,stdout),C=-;}

 inline void print(int x){

     if(C><<)Ot();if(x<)sr[++C]=,x=-x;

     while(z[++Z]=x%+,x/=);

     while(sr[++C]=z[Z],--Z);sr[++C]='\n';

 }

 const int N=;

 struct EE{

     int u,v,h;

     EE(){}

     EE(int u,int v,int h):u(u),v(v),h(h){}

     inline bool operator <(const EE &b)const

     {return h>b.h;}

 }E[N];

 struct node{

     int u,dis;

     node(){}

     node(int u,int dis):u(u),dis(dis){}

     inline bool operator <(const node &b)const

     {return dis>b.dis;}

 };

 int head[N],Next[N],ver[N],edge[N],tot;

 int hc[N],nc[N],vc[N],tc;

 int val[N],f[N][],fa[N],dis[N],vis[N],mn[N],bin[];

 int n,m,ans,k;

 priority_queue<node> q;

 inline void clear(){

     memset(head,,sizeof(head)),tot=;

     memset(hc,,sizeof(hc)),tc=;

     memset(mn,0x3f,sizeof(mn));

     memset(f,,sizeof(f));

 }

 inline void add(int u,int v,int e){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;

 }

 inline void addc(int u,int v){

     vc[++tc]=v,nc[tc]=hc[u],hc[u]=tc;

 }

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

 inline void mission(int u){

     for(int i=;bin[i]<=n;++i)

     f[u][i]=f[f[u][i-]][i-];

 }

 void dijkstra(int s=){

     memset(vis,,sizeof(vis));

     memset(dis,0x3f,sizeof(dis));

     q.push(node(s,)),dis[s]=;

     while(!q.empty()){

         int u=q.top().u;q.pop();

         if(vis[u]) continue;

         vis[u]=;

         for(int i=head[u];i;i=Next[i]){

             int v=ver[i];

             if(cmin(dis[v],dis[u]+edge[i])) q.push(node(v,dis[v]));

         }

     }

     memcpy(mn+,dis+,sizeof(int)*(n));

 }

 void dfs(int u){

     mission(u);

     for(int i=hc[u];i;i=nc[i]){

         int v=vc[i];

         dfs(v),cmin(mn[u],mn[v]);

     }

 }

 inline int query(int u,int x){

     for(int i=;~i;--i)

     if(f[u][i]&&val[f[u][i]]>x) u=f[u][i];

     return mn[u];

 }

 void kruskal(){

     int cnt=n;

     for(int i=;i<=(n<<);++i) fa[i]=i;

     sort(E+,E++m);

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

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

         if(u!=v){

             val[++cnt]=E[i].h;

             f[u][]=f[v][]=cnt,fa[u]=fa[v]=cnt;

             addc(cnt,u),addc(cnt,v);

             if(cnt-n==n-) break;

         }

     }

     dfs(cnt);

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     int T=read();

     bin[]=;for(int i=;i<=;++i) bin[i]=bin[i-]<<;

     while(T--){

         n=read(),m=read(),ans=;

         clear();

         for(int i=,u,v,e,h;i<=m;++i){

             u=read(),v=read(),e=read(),h=read(),E[i]=EE(u,v,h);

             add(u,v,e),add(v,u,e);

         }

         dijkstra();

         kruskal();

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

         while(q--){

             int u=(k*ans+read()-)%n+,v=(k*ans+read())%(s+);

             print(ans=query(u,v));

         }

     }

     Ot();

     return ;

 }