#include<bits/stdc++.h>
using namespace std;
int n,m,rt[1000010],cnt;
struct node{
    int fa,ls,rs,deep,minn;
}t[6000010];
int build(int l,int r){
    int u=++cnt;
    if(l==r){
        t[u].fa=l;
        return u;
    }
    int mid=(l+r)/2;
    t[u].ls=build(l,mid);
    t[u].rs=build(mid+1,r);
    return u;
}
int query(int u,int l,int r,int x){
    if(l==r) return u;
    int mid=(l+r)/2;
    if(mid>=x) return query(t[u].ls,l,mid,x);
    else return query(t[u].rs,mid+1,r,x);
}
int find_root(int u,int a){
    int fa=query(rt[u],1,n,a);
    if(t[fa].fa==a) return fa;
    return find_root(u,t[fa].fa);
}
int marge(int u,int l,int r,int x,int f,int minn){
    int d=++cnt;
    t[d]=t[u];
    if(l==r){
        t[d].fa=f;
        t[d].minn=min(t[d].minn,minn);
        return d;
    }
    int mid=(l+r)/2;
    if(mid>=x) t[d].ls=marge(t[u].ls,l,mid,x,f,minn);
    else t[d].rs=marge(t[u].rs,mid+1,r,x,f,minn);
    t[d].minn=min({t[d].minn,t[t[d].ls].minn,t[t[d].rs].minn,minn});
    return d;
}
int add(int u,int l,int r,int x,int minn){
    int d=++cnt;
    t[d]=t[u];
    if(l==r){
        t[d].deep++;
        return d;
    }
    int mid=(l+r)/2;
    if(mid>=x) t[d].ls=add(t[u].ls,l,mid,x,minn);
    else t[d].rs=add(t[u].rs,mid+1,r,x,minn);
    t[d].minn=min({t[d].minn,minn,t[t[d].ls].minn,t[t[d].rs].minn});
    return d;
}
void merge(int u,int a,int b,int minn){
    rt[u]=rt[u-1];
    a=find_root(u,a),b=find_root(u,b);
    if(t[a].fa!=t[b].fa){
        if(t[a].deep>t[b].deep) swap(a,b);
        rt[u]=marge(rt[u-1],1,n,t[a].fa,t[b].fa,minn);
        if(t[a].deep==t[b].deep) rt[u]=add(rt[u],1,n,t[b].fa,minn);
    }
}
struct nodee{
    int u,v,l,a;
    bool operator<(const nodee t)const{
        return a>t.a;
    }
}no[400010];
vector<pair<int,int> >e[200010];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int dis[200010];
bool flag[200010];
void dij(){
    memset(dis,0x3f,sizeof(dis));
    memset(flag,0,sizeof(flag));
    dis[1]=0;
    q.push({0,1});
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(flag[u]) continue;
        flag[u]=1;
        for(auto v:e[u]) if(dis[v.first]>dis[u]+v.second){
            dis[v.first]=dis[u]+v.second;
            q.push({dis[v.first],v.first});
        }
    }
}
void solve(){
    memset(t,0,sizeof(t));
    for(int i=1;i<=6000000;i++) t[i].minn=INT_MAX;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) e[i].clear();
    rt[0]=build(1,n);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&no[i].u,&no[i].v,&no[i].l,&no[i].a);
        e[no[i].u].push_back({no[i].v,no[i].l});
        e[no[i].v].push_back({no[i].u,no[i].l});
    }
    dij();
    sort(no+1,no+1+m);
    for(int i=1;i<=m;i++){
        rt[i]=rt[i-1];
        int u=find_root(i,no[i].u),v=find_root(i,no[i].v);
        if(u==v) continue;
        merge(i,u,v,min(dis[no[i].u],dis[no[i].v]));
    }
    int q,k,s,lastans=0;
    scanf("%d%d%d",&q,&k,&s);
    for(int i=1;i<=q;i++){
        int v,p;
        scanf("%d%d",&v,&p);
        v=(v+k*lastans-1)%n+1;
        p=(p+k*lastans)%(s+1);
        int l=0,r=m,ans=0;
        while(l<=r){
            int mid=(l+r)/2;
            if(no[mid].a>p) l=mid+1,ans=mid;
            else r=mid-1;
        }
        if(ans==0){
            printf("%d\n",lastans=dis[v]);
            continue;
        }
        if(l==m+1){
            printf("%d\n",lastans=0);
            continue;
        }
        printf("%d\n",(lastans=min(dis[v],t[find_root(ans,v)].minn)));
    }
}
signed main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}