//Achen

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<vector>

#include<cmath>

#include<queue>

#include<set>

#define Formylove return 0

#define For(i,a,b) for(int i=(a);i<=(b);i++)

#define Rep(i,a,b) for(int i=(a);i>=(b);i--)

#define inf 1e18

const int N=;

typedef long long LL;

typedef double db;

using namespace std;

int T,n,m,Q,K,S;

template<typename T> void read(T &x) {

    char ch=getchar(); T f=; x=;

    while((ch!='-')&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

}

struct edge {

    int u,v,l,a;

    edge(){}

    edge(int u,int v,int a):u(u),v(v),a(a){}

    friend bool operator <(const edge&A,const edge&B) {

        return A.a>B.a;

    }

}e[N];

int ec,fir[N],nxt[N],to[N],val[N];

void add(int u,int v,int w) {

    nxt[++ec]=fir[u]; fir[u]=ec; to[ec]=v; val[ec]=w;

    nxt[++ec]=fir[v]; fir[v]=ec; to[ec]=u; val[ec]=w;

}

int fa[N];

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

int f[N][],vv[N];

int ec2,fi[N],nx[N],tt[N];

void ADD(int u,int v) {

    nx[++ec2]=fi[u]; fi[u]=ec2; tt[ec2]=v;

}

LL fans[N],dis[N];

void dfs(int x,int F) {

    f[x][]=F;

    fans[x]=inf;

    if(x<=n) fans[x]=dis[x];

    For(i,,) f[x][i]=f[f[x][i-]][i-];

    for(int i=fi[x];i;i=nx[i]) {

        dfs(tt[i],x);

        fans[x]=min(fans[x],fans[tt[i]]);

    }

}

int totnode;

void kruskal(int n) {

    sort(e+,e+m+);

    totnode=n;

    For(i,,n*) fa[i]=i;

    For(i,,m) {

        int x=e[i].u,y=e[i].v;

        int fx=find(x),fy=find(y);

        if(fx!=fy) {

            totnode++;

            vv[totnode]=e[i].a;

            ADD(totnode,fx); ADD(totnode,fy);

            fa[fx]=fa[fy]=totnode;

        }

    }

    dfs(totnode,);

}

struct node {

    int u; LL d;

    node(int u,LL d):u(u),d(d){}

    friend bool operator <(const node&A,const node&B) {

        return A.d>B.d;

    }

};

priority_queue<node>que;

int vis[N];

void dijkstra(int s) {

    For(i,,n) dis[i]=inf,vis[i]=;

    dis[s]=;

    que.push(node(s,));

    while(!que.empty()) {

        node tp=que.top();

        que.pop();

        if(vis[tp.u]||dis[tp.u]!=tp.d) continue;

        vis[tp.u]=;

        for(int i=fir[tp.u];i;i=nxt[i]) {

            int y=to[i];

            if(dis[y]>dis[tp.u]+val[i]) {

                dis[y]=dis[tp.u]+val[i];

                que.push(node(y,dis[y]));

            }

        }

    }

}

void init() {

    ec=ec2=;

    memset(fir,,sizeof(fir));

    memset(fi,,sizeof(fi));

}

int main() {

#ifdef ANS

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

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

#endif

    read(T);

    while(T--) {

        init();

        read(n); read(m);

        For(i,,m) {

            int u,v,l,a;

            read(u); read(v); read(l); read(a);

            add(u,v,l);

            e[i]=edge(u,v,a);

        }

        dijkstra();

        kruskal(n);

        read(Q); read(K); read(S);

        LL ans=;

        while(Q--) {

            int v0,p0;

            read(v0); read(p0);

            int x=(v0+ans%n*K%n-)%n+;

            int p=(p0+ans%(S+)*K%(S+))%(S+);

            Rep(i,,) if(f[x][i]&&vv[f[x][i]]>p)

                x=f[x][i];

            ans=fans[x];

            printf("%lld\n",ans);

        }

    }

    Formylove;

}