#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define mp make_pair

#define int long long

#define P pair<int,int>

#define t(i) edge[i].to

#define w(i) edge[i].wei

#define fy(i) edge_krus[i].wei

#define ri register int

#define rc register char

#define rb register bool

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+,M=+;

int ed_cnt,ed_tr_cnt,head[N],as[N<<],fat[N<<][],nod_cnt,n,m,fa[N<<],lstas,val[N<<];

bool vis[N];

struct ed{int to,nxt,wei;}edge[M<<];

struct ed_tr{int fr,to,wei;}edge_krus[M];

il int read()

{

    rc ch=gc;ri x=;rb y=;

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

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il bool cmp(ed_tr gd,ed_tr gs){return gd.wei>gs.wei;}

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

il void ad(ri x,ri y,ri z){edge[++ed_cnt]=(ed){x,head[y],z};head[y]=ed_cnt;}

il void dij()

{

    priority_queue< P,vector<P>,greater<P> >Q;

    memset(vis,,sizeof(vis));memset(as,,sizeof(as));as[]=;Q.push(mp(,));

    while(!Q.empty())

    {

        ri nw=Q.top().second;Q.pop();if(vis[nw])continue;vis[nw]=;

        e(i,nw)if(as[t(i)]>as[nw]+w(i))as[t(i)]=as[nw]+w(i),Q.push(mp(as[t(i)],t(i)));

    }

}

il int jump(ri x,ri y){my(i,,)if(val[fat[x][i]]>y)x=fat[x][i];return x;}

signed main()

{

    freopen("return.in","r",stdin);freopen("return.out","w",stdout);

    ri T=read();

    while(T--)

    {

        n=read();m=read();rp(i,,n<<)fa[i]=i;nod_cnt=n;ed_cnt=;memset(head,,sizeof(head));lstas=;

        rp(i,,m){ri x=read(),y=read(),z=read(),p=read();ad(x,y,z);ad(y,x,z);edge_krus[i]=(ed_tr){x,y,p};}

        dij();sort(edge_krus+,edge_krus++m,cmp);

        //rp(i,1,n)printf("as[%d]=%d\n",i,as[i]);

        rp(i,,m)

        {

            ri x=fd(edge_krus[i].fr),y=fd(edge_krus[i].to);if(x==y)continue;

            //printf("x=%d y=%d z=%d fy=%d\n",edge_krus[i].fr,edge_krus[i].to,edge_krus[i].wei,fy(i));

            fa[x]=fa[y]=fat[x][]=fat[y][]=++nod_cnt;as[nod_cnt]=min(as[x],as[y]);val[nod_cnt]=fy(i);

            //printf("val[fa[%d]=fa[%d]=%d]=%d nod_cnt=%d\n",x,y,fa[x],val[fa[x]],nod_cnt);

        }

        rp(i,,)rp(j,,nod_cnt)fat[j][i]=fat[fat[j][i-]][i-];

        ri Q=read(),k=read(),s=read();

        while(Q--)

        {

            ri x=(read()+k*lstas-)%n+,y=(read()+k*lstas)%(s+);printf("%lld\n",lstas=as[jump(x,y)]);

        }

    }

    return ;

}