#include <iostream>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <cstring>

using namespace std;

const int N = 4e5 + , oo = 1e9 + ;

struct Node {

    int u, v, len, high, nxt;

} E[N], G[N << ], Edge[N << ];

struct Node_ {

    int u, dis_;

    inline bool operator < (const Node_ a) const {return dis_ > a.dis_;}

};

int head_1[N], head_2[N << ], now;

int dis[N << ];

bool vis[N];

int fa[N << ];

int n, m;

int High[N << ];

int f[N << ][];

int deep[N << ];

#define gc getchar()

inline int read() {

    int x = ;

    char c = gc;

    while(c < '' || c > '') c = gc;

    while(c >= '' && c <= '') x = x *  + c - '', c = gc;

    return x;

}

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

inline bool Cmp(Node a, Node b) {return a.high > b.high;}

void Dfs(int u, int fa) {for(int i = head_2[u]; ~ i; i = G[i].nxt) if(G[i].v != fa) f[G[i].v][] = u, Dfs(G[i].v, u);}

inline int Jump(int X, int H) {for(int i = ; i >= ; i --) if(f[X][i] && High[f[X][i]] > H) X = f[X][i];return X;}

inline void Add_Edge(int u, int v, int Len) {Edge[++ now].v = v; Edge[now].len = Len; Edge[now].nxt = head_1[u]; head_1[u] = now;}

inline void Add_G(int u, int v) {G[++ now].v = v; G[now].nxt = head_2[u]; head_2[u] = now;}

inline void Pre() {for(int i = ; i <= ; i ++) for(int j = ; j <= (n *  - ); j ++) f[j][i] = f[f[j][i - ]][i - ];}

inline void Dijkstra() {

    for(int i = ; i <= n; i ++) dis[i] = oo;

    for(int i = ; i <= n; i ++) vis[i] = ;

    priority_queue <Node_> Q;

    Q.push((Node_) {, });

    dis[] = ;

    while(!Q.empty()) {

        Node_ topp = Q.top();

        Q.pop();

        if(vis[topp.u]) continue;

        vis[topp.u] = ;

        for(int i = head_1[topp.u]; ~ i; i = Edge[i].nxt)

            if(dis[Edge[i].v] > dis[topp.u] + Edge[i].len) {

                dis[Edge[i].v] = dis[topp.u] + Edge[i].len;

                Q.push((Node_) {Edge[i].v, dis[Edge[i].v]});

            }

    }

}

inline void Kruskal() {

    sort(E + , E + m + , Cmp);

    for(int i = ; i <= (n << ); i ++) fa[i] = i;

    for(int i = ; i <= (n << ); i ++) head_2[i] = -;

    int cnt = n;

    now = ;

    for(int i = ; i <= m; i ++) {

        if(cnt == n *  - ) break;

        int u = E[i].u, v = E[i].v, fau = Get(u), fav = Get(v);

        if(fau != fav) {

            fa[fau] = fa[fav] = ++ cnt;

            High[cnt] = E[i].high;

            dis[cnt] = min(dis[fau], dis[fav]);

            Add_G(fau, cnt), Add_G(cnt, fau), Add_G(fav, cnt), Add_G(cnt, fav);

        }

    }

}

int main() {

    for(int T = read(); T; T --) {

        memset(f, , sizeof f);

        n = read(), m = read(); now = ;

        for(int i = ; i <= n; i ++) head_1[i] = -;

        for(int i = ; i <= m; i ++) {

            int u = read(), v = read(), Len = read(), high = read();

            Add_Edge(u, v, Len), Add_Edge(v, u, Len);

            E[i] = (Node) {u, v, Len, high};

        }

        Dijkstra(), Kruskal(), Dfs( * n - , ), Pre();

        int Q = read(), K = read(), S = read(), Lastans = ;

        for(; Q; Q --) {

            int X = (read() + K * Lastans - ) % n + , H = (read() + K * Lastans) % (S + );

            Lastans = dis[Jump(X, H)]; cout << Lastans << "\n";

        }

    }

    return ;

}