1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 400005

 4 struct ji1{

 5     int x,y,z;

 6     bool operator < (const ji1 &k)const{

 7         return z>k.z;

 8     }

 9 }e[N];

10 struct ji2{

11     int nex,to,len;

12 }edge[N<<1];

13 struct ji3{

14     int k,d;

15     bool operator < (const ji3 &x)const{

16         return d>x.d;

17     }

18 };

19 priority_queue<ji3>q;

20 int T,E,n,m,x,y,z,w,ans,head[N],d[N],vis[N],v[N],ls[N],rs[N],f[N][21];

21 int find(int k){

22     if (k==f[k][0])return k;

23     return f[k][0]=find(f[k][0]);

24 }

25 void add(int x,int y,int z){

26     edge[E].nex=head[x];

27     edge[E].to=y;

28     edge[E].len=z;

29     head[x]=E++;

30 }

31 void dij(){

32     for(int i=2;i<=n;i++)d[i]=2e9;

33     memset(vis,0,sizeof(vis));

34     q.push(ji3{1,0});

35     while (!q.empty()){

36         int k=q.top().k;

37         q.pop();

38         if (vis[k])continue;

39         vis[k]=1;

40         for(int i=head[k];i!=-1;i=edge[i].nex){

41             int v=edge[i].to;

42             if (d[v]>d[k]+edge[i].len)q.push(ji3{v,d[v]=d[k]+edge[i].len});

43         }

44     }

45 }

46 void dfs(int k){

47     for(int i=1;i<=20;i++)f[k][i]=f[f[k][i-1]][i-1];

48     if (k<=n)return;

49     f[ls[k]][0]=f[rs[k]][0]=k;

50     dfs(ls[k]);

51     dfs(rs[k]);

52 }

53 int query(int k,int w){

54     for(int i=20;i>=0;i--)

55         if (w<v[f[k][i]])k=f[k][i];

56     return d[k];

57 }

58 int main(){

59     scanf("%d",&T);

60     while (T--){

61         scanf("%d%d",&n,&m);

62         memset(head,-1,sizeof(head));

63         E=ans=0;

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

65             scanf("%d%d%d%d",&x,&y,&z,&w);

66             add(x,y,z);

67             add(y,x,z);

68             e[i]=ji1{x,y,w};

69         }

70         dij();

71         for(int i=1;i<2*n;i++)f[i][0]=i;

72         sort(e+1,e+m+1);

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

74             x=find(e[i].x);

75             y=find(e[i].y);

76             if (x==y)continue;

77             v[++n]=e[i].z;

78             d[n]=min(d[x],d[y]);

79             ls[n]=x;

80             rs[n]=y;

81             f[x][0]=f[y][0]=n;

82         }

83         n=n/2+1;

84         dfs(2*n-1);

85         scanf("%d%d%d",&m,&z,&w);

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

87             scanf("%d%d",&x,&y);

88             printf("%d\n",ans=query((x+z*ans-1)%n+1,(y+z*ans)%(w+1)));

89         }

90     }

91 }