#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define pb push_back

const ld pi = 3.14159265358979323846;

int mod = 998244353;
ll INF = (ll)1e18;

template<typename T>
T chmax(T a, T b) {
    return a > b ? a : b;
}

template<typename T>
T chmin(T a, T b) {
    return a > b ? b : a;
}

const int N = (int)4e6 + 1, M = N * 2, S = 21;

struct Kruskal {
    vector<int> h, w, e, ne, node, dep;
    vector<vector<int>> fa, kr;
    int n, idx, t;

    const int depth = 21;

    Kruskal(int _n) {
        n = _n;
        idx = 0;

        dep.resize(n * 4 + 1, (int)1e9);
        fa.resize(n * 4 + 1);

        ne.resize(n * 4 + 1, 0);
        h.resize(n * 4 + 1, -1);
        e.resize(n * 4 + 1, 0);
        w.resize(n * 4 + 1, 0);

        node.resize(n * 4 + 1, 0);

        for (int i = 0; i <= n * 4; i++) {
            fa[i] = vector<int>(depth + 1);
            node[i] = i;
        }
    }

    int find(int x) {
        return x == node[x] ? x : node[x] = find(node[x]);
    }

    void build(int u, int v) {
        e[idx] = v, ne[idx] = h[u], h[u] = idx++;
        e[idx] = u, ne[idx] = h[v], h[v] = idx++;
    }

    void kruskal() {
        for (int k = n, i = 1; i <= kr.size(); i++) {
            int du = find(kr[i - 1][0]), dv = find(kr[i - 1][1]);

            if (du != dv) {
                node[du] = node[dv] = ++k;
                w[k] = kr[i - 1][2];
                build(k, du);
                build(k, dv);
                t = k;

                if (k == 2 * n - 1) {
                    break;
                }
            }
        }
    }

    void bfs(int rt) {
        dep[rt] = 1;
        dep[0] = 0;

        queue<int> q;
        q.push(rt);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int i = h[u]; i != -1; i = ne[i]) {
                int j = e[i];

                if (dep[j] > dep[u] + 1) {
                    dep[j] = dep[u] + 1;

                    q.push(j);
                    fa[j][0] = u;

                    for (int k = 1; k < depth; k++) {
                        fa[j][k] = fa[fa[j][k - 1]][k - 1];
                    }
                }
            }
        }
    }

    int lca(int u, int v) {
        if (find(u) != find(v))
            return -1;

        if (dep[u] < dep[v])
            swap(u, v);

        for (int i = depth - 1; i >= 0; i--) {
            if (dep[fa[u][i]] >= dep[v]) {
                u = fa[u][i];
            }
        }

        if (u == v)
            return u;

        for (int i = depth - 1; i >= 0; i--) {
            if (fa[u][i] != fa[v][i]) {
                u = fa[u][i];
                v = fa[v][i];
            }
        }

        return fa[u][0];
    }
};

ll h[N], f[N], v[N], e[M], ne[M], w[M], dp[M], n, m, idx;

void add(int u, int v, int c) {
    e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx++;
}

bool cmp(vector<int> a, vector<int> b) {
    return a[2] > b[2];
}

void dfs(int u, int fa, const Kruskal &kr) {
    for (int i = kr.h[u]; i != -1; i = kr.ne[i]) {
        int j = kr.e[i];

        if (j == fa)
            continue;

        dfs(j, u, kr);
        dp[u] = chmin(dp[u], dp[j]);
    }

    dp[u] = chmin(dp[u], f[u]);
}

void solve() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        h[i] = -1;
    }

    idx = 0;

    Kruskal kr(n);

    for (int i = 0; i < m; i++) {
        int u, v, l, a;
        cin >> u >> v >> l >> a;

        add(u, v, l);
        add(v, u, l);

        kr.kr.pb({u, v, a});
    }

    ll qr, k, s, d = 0;
    cin >> qr >> k >> s;

    if (!m)
        return;

    sort(kr.kr.begin(), kr.kr.end(), cmp);

    for (int i = 0; i <= n * 10 + 1; i++) {
        f[i] = dp[i] = INF;
        v[i] = 0;
    }

    f[1] = dp[1] = f[0] = dp[0] = 0;

    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> q;
    q.push({0, 1});

    while (!q.empty()) {
        auto p = q.top();
        q.pop();

        ll u = p.second;

        if (v[u])
            continue;

        v[u] = 1;

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];

            if (f[j] > f[u] + w[i]) {
                f[j] = f[u] + w[i];
                q.push({f[j], j});
            }
        }
    }

    kr.kruskal();
    kr.bfs(kr.t);

    dfs(kr.t, -1, kr);

    for (int i = 0; i < qr; i++) {
        ll v0, p0;
        cin >> v0 >> p0;

        ll v = (v0 + k * d % n - 1 + n) % n + 1;
        ll p = (p0 + k * d % (s + 1)) % (s + 1);

        for (int i = 20; i >= 0; i--) {
            if (!kr.fa[v][i])
                continue;

            if (kr.w[kr.fa[v][i]] > p) {
                v = kr.fa[v][i];
            }
        }

        cout << (d = dp[v]) << endl;
    }
}

signed main() {
    freopen("return.in", "r", stdin);
    freopen("return.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(0);

    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}