#include<iostream>
#include<algorithm>
#include<numeric>
#include<vector>
#include<limits>
#include<queue>
using ll=long long;
using piit=std::pair<ll,int>;
const int sz=2e5+10;
const ll inf=std::numeric_limits<ll>::max()/2;
struct edge{
    int u,v,c;
    bool operator<(const edge &a)const{
        return c>a.c;
    }
}g[sz<<1];
int carr[sz];
std::vector<piit>graph[sz];
ll dis[sz];
bool vis[sz];
std::priority_queue<piit,std::vector<piit>,std::greater<piit>>pq;
void dijkstra(int s){
    dis[s]=0,pq.push(std::make_pair(0,s));
    while(!pq.empty()){
        int u=pq.top().second;
        pq.pop();
        if(vis[u])continue;
        vis[u]=true;
        for(auto p:graph[u]){
            int v=p.second;
            if(dis[v]>dis[u]+p.first){
                dis[v]=dis[u]+p.first;
                pq.push(std::make_pair(dis[v],v));
            }
        }
    }
}
template<class __Tp>
struct Array{
    struct node{
        int lson,rson;
        __Tp val;
    }tree[sz<<7];
    int num=0;
    void build(int &p,int ln,int rn,__Tp arr[]){
        p=++num;
        if(ln==rn)return tree[p].val=arr[ln],void();
        int mid=ln+rn>>1;
        build(tree[p].lson,ln,mid,arr);
        build(tree[p].rson,mid+1,rn,arr);
    }
    void modify(int &p,int srt,int ln,int rn,int pos,__Tp val){
        p=++num,tree[p]=tree[srt];
        if(ln==rn)return tree[p].val=val,void();
        int mid=ln+rn>>1;
        if(pos<=mid)modify(tree[p].lson,tree[srt].lson,ln,mid,pos,val);
        else modify(tree[p].rson,tree[srt].rson,mid+1,rn,pos,val);
    }
    void add(int &p,int srt,int ln,int rn,int pos,__Tp val){
        p=++num,tree[p]=tree[srt];
        if(ln==rn)return tree[p].val+=val,void();
        int mid=ln+rn>>1;
        if(pos<=mid)add(tree[p].lson,tree[srt].lson,ln,mid,pos,val);
        else add(tree[p].rson,tree[srt].rson,mid+1,rn,pos,val);
    }
    __Tp query(int p,int ln,int rn,int pos){
        if(ln==rn)return tree[p].val;
        int mid=ln+rn>>1;
        if(pos<=mid)return query(tree[p].lson,ln,mid,pos);
        return query(tree[p].rson,mid+1,rn,pos);
    }
};
int rtf[sz],rts[sz],rtm[sz],arr[sz],n,m,q,k,s,f;
struct UFS{
    Array<int>fa,ssz;
    Array<ll>min;
    void clear(int n){
        std::fill(fa.tree+1,fa.tree+fa.num+1,Array<int>::node{0,0,0});
        std::fill(ssz.tree+1,ssz.tree+ssz.num+1,Array<int>::node{0,0,0});
        std::fill(min.tree+1,min.tree+min.num+1,Array<ll>::node{0,0,0});
        fa.num=ssz.num=min.num=0;
        std::iota(arr+1,arr+n+1,1);
        fa.build(rtf[f],1,n,arr);
        std::fill(arr+1,arr+n+1,1);
        ssz.build(rts[f],1,n,arr);
        std::fill(dis+1,dis+n+1,inf);
        std::fill(vis+1,vis+n+1,0);
        dijkstra(1);
        min.build(rtm[f],1,n,dis);
    }
    int find(int vrt,int u){
        int fu=fa.query(rtf[vrt],1,n,u);
        if(fu==u)return u;
        return find(vrt,fu);
    }
    void merge(int vrt,int u,int v){
        int fu=find(vrt,u),fv=find(vrt,v);
        if(fu==fv)return;
        if(ssz.query(rts[vrt],1,n,fu)>ssz.query(rts[vrt],1,n,fv))std::swap(fu,fv);
        fa.modify(rtf[vrt],rtf[vrt],1,n,fu,fv);
        ssz.add(rts[vrt],rts[vrt],1,n,fv,ssz.query(rts[vrt],1,n,fu));
        ll mu=min.query(rtm[vrt],1,n,fu),mv=min.query(rtm[vrt],1,n,fv);
        min.modify(rtm[vrt],rtm[vrt],1,n,fv,std::min(mu,mv));
    }
    ll qmin(int vrt,int u){
        int fu=find(vrt,u);
        return min.query(rtm[vrt],1,n,fu);
    }
}ufs;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin>>t;
    while(t--){
        std::cin>>n>>m;
        for(int i=1;i<=n;i++)graph[i].clear();
        for(int i=1;i<=m;i++){
            int u,v,l,a;
            std::cin>>u>>v>>l>>a;
            graph[u].push_back(std::make_pair(l,v));
            graph[v].push_back(std::make_pair(l,u));
            g[i]=edge{u,v,a},carr[i]=a;
        }
        std::sort(carr+1,carr+m+1);
        f=std::unique(carr+1,carr+m+1)-carr;
        for(int i=1;i<=m;i++)
            g[i].c=std::lower_bound(carr+1,carr+f,g[i].c)-carr;
        ufs.clear(n);
        std::sort(g+1,g+m+1),g[0].c=f;
        for(int i=1,j=1;i<=m;i=j){
            rtf[g[i].c]=rtf[g[i-1].c];
            rts[g[i].c]=rts[g[i-1].c];
            rtm[g[i].c]=rtm[g[i-1].c];
            while(j<=m&&g[j].c==g[i].c)
                ufs.merge(g[j].c,g[j].u,g[j].v),j++;
        }
        std::cin>>q>>k>>s,s++;
        ll lans=0;
        while(q--){
            int v,p;
            std::cin>>v>>p;
            v=(1ll*v+k*lans-1)%n+1,p=(1ll*p+k*lans)%s;
            p=std::upper_bound(carr+1,carr+f,p)-carr;
            lans=ufs.qmin(p,v);
            std::cout<<lans<<"\n";
        }
    }
    return 0;
}