#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
//#define int long long
using namespace std;
struct node{
    int u,v,l,a;
    bool operator <(const node b)const{
        return a>b.a;
    }
}s[400005],p[400005];
int ff[400005],val[400005];
int son[400005][2];
int find(int x){
    if (!ff[x])return x;
    else return ff[x]=find(ff[x]);
}
int h[200005],e[800005],ne[800005],le[800005],idx;
void add(int a,int b,int c){
    e[++idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    le[idx]=c;
}
int vis[200005],dis[400005];
void dijkstra(){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push({0,1});
    while (!q.empty()){
        int u=q.top().second;
        q.pop();
        if (vis[u])continue;
        vis[u]=1;
        for (int i=h[u];i;i=ne[i]){
            int v=e[i];
            if (dis[v]>dis[u]+le[i]){
                dis[v]=dis[u]+le[i];
                q.push({dis[v],v});
            }
        }
    }
}
int fa[400005][20],depth[400005];
void dfs(int u,int ft){
    //cout<<u<<" "<<son[u][0]<<" "<<son[u][1]<<"\n";
    fa[u][0]=ft;
    depth[u]=depth[ft]+1;
    for (int i=1;i<=19;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    if (son[u][0]){
        dfs(son[u][0],u);
        dfs(son[u][1],u);
        dis[u]=min(dis[son[u][0]],dis[son[u][1]]);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t,n,m;
    cin>>t;
    while (t--){
    //memset(fa,0,sizeof(fa));
    memset(h,0,sizeof(h));
    memset(e,0,sizeof(e));
    memset(ne,0,sizeof(ne));
    memset(le,0,sizeof(le));
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    memset(depth,0,sizeof(depth));
    memset(ff,0,sizeof(ff));
    memset(val,0,sizeof(val));
    memset(s,0,sizeof(s));
    memset(p,0,sizeof(p));
    memset(son,0,sizeof(son));
    dis[1]=0;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>s[i].u>>s[i].v>>s[i].l>>s[i].a;
        add(s[i].u,s[i].v,s[i].l);
        add(s[i].v,s[i].u,s[i].l);
    }
    dijkstra();
    
    sort(s+1,s+1+m);
    int cnt=n;
    for (int i=1;i<=m;i++){
        //cout<<s[i].u<<" "<<s[i].v<<"\n";
        int u=find(s[i].u),v=find(s[i].v);
        if (u==v)continue;
        ff[u]=ff[v]=++cnt;
        son[cnt][0]=u,son[cnt][1]=v;
        val[cnt]=s[i].a;
    }
    dfs(cnt,0);
    int q,k,s,lastans=0;
    cin>>q>>k>>s;
    while (q--){
        int v,w;
        cin>>v>>w;
        v=(v+k*lastans-1)%n+1;
        w=(w+k*lastans)%(s+1);
        for (int i=19;i>=0;i--){
            if (val[fa[v][i]]>w)v=fa[v][i];
        }
        cout<<(lastans=dis[v])<<"\n";
    }
    }
    return 0;
}