#include<bits/stdc++.h>
#define rep(i,j,k) for(int i = (j) ; i <= (k) ; i++)
#define frep(i,j,k) for (int  i = (j) ; i >= (k) ; i--)
#define debug puts("Debeg!!!!! wake up !!!")
#define Mset(a,v) memset(a,v,sizeof (a))
#define Mcpy(a,v) memcpy(a,v,sizeof (a))
#define mrep(i,j) for(int i=(h[j]);~i;i=ne[i])

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

const int N = 5005;
const int M = 2e6+9;
const int INF=1e8;
const double eps= 1e-8;
int n,m;
int fa[N];
bool vis[N];
LL d[N],w[M],g[N];
int h[N],e[M],ne[M],idx;
int f[N][23];
LL val[N];
int cnt;


struct que
{
    int id;
    LL dis;
    bool operator < (const que & rhs) const
    {
        return dis < rhs.dis;
    }
};

void add(int x,int y,LL z)
{
    ne[++idx] = h[x];
    h[x] = idx;
    e[idx] = y;
    w[idx] = z;
}

struct node
{
    int a,b;
    LL h;

    void init()
    {
        LL c;
        cin >> a >> b;
        cin >> c >> h;
        add(a,b,c); add(b,a,c);
    }

    bool operator < (const node & rhs) const
    {
        return h > rhs.h;
    }

}E[M];

void dij(int s)
{
    priority_queue<que>q;
    Mset(d,127);
    Mset(vis,0);

    d[s] = 0;
    q.push({s,0});
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        int id = t.id;
        LL dis = t.dis;
        if(vis[id]) continue;
        vis[id] = 1;

        mrep(i,id)
        {
            int v = e[i];
            if(d[v] > d[id] + w[i])
            {
                d[v] = d[id] + w[i];
                q.push({v,d[v]});
            }
        }
    }
}

int getfa(int x)
{
    if(fa[x]==x)return x;
    else return fa[x] = getfa(fa[x]);
}

void dfs(int u)
{
    g[u] = d[u];
    mrep(i,u)
    {
        int v = e[i];
        f[v][0] = u;
        dfs(v);
        g[u] = min(g[u],g[v]);
    }
}

void kuruscal()
{
    sort(E+1,E+1+m);
    Mset(h,-1);
    idx = 0;

    rep(i,1,n) fa[i] = i;
    rep(i,1,m)
    {
        int pa = getfa(E[i].a);
        int pb = getfa(E[i].b);
        if(pa == pb) continue;
        val[++cnt] = E[i].h;
        fa[pa] = fa[pb] = fa[cnt]  = cnt;

        add(cnt,pa,0);
        add(cnt,pb,0);
    }

    dfs(cnt);
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        Mset(h,-1);
        Mset(f,0);
        Mset(g,127);
        idx =  0;


        rep(i,1,m) E[i].init();
        cnt = n;

        LL q,k,s;
        LL lastans = 0;
        dij(1);
        kuruscal();

        for(int i = 1 ; (1<<i) <= cnt ; i ++)
                rep(j,1,cnt) f[j][i] = f[f[j][i-1]][i-1];

        cin >> q >> k >> s;
        while (q--)
        {
            int v,p;
            cin >> v >> p;
            v = (v + k * lastans -1)%n +1;
            p = (p + k * lastans ) % (s+1);


            frep(i,22,0) if(f[v][i] && val[f[v][i]] > p) v = f[v][i];

            lastans = g[v];

            cout << lastans << endl;
            puts("");
        }
    }


}