简单题。

一眼求出最大生成树作一个 Kruskal 重构树。
然后稍微想一想会发现干一个倍增，dijkstra 预处理每个点到 1 的最短距离，直接做一个子树 Min 即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 15, M = N << 1, INF = 0x3f3f3f3f;

int T;
int n, m, lst = 0;

struct Graph {
    int h[N], e[M], w[M], ne[M], idx;
    void init() {
        for (int i = 1; i <= n; i++) h[i] = -1;
        idx = 0;
    }
    void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }

    int d[N];
    bool st[N];
    priority_queue< pair<int, int> > q;
    void dijkstra() {
        for (int i = 1; i <= n; i++) d[i] = INF, st[i] = 0;
        while (q.size()) q.pop();

        d[1] = 0, q.push(make_pair(0, 1));
        while (q.size()) {
            int u = q.top().second; q.pop();
            if (st[u]) continue;
            st[u] = 1;
            for (int i = h[u]; ~i; i = ne[i]) {
                int v = e[i];
                if (d[v] > d[u] + w[i]) {
                    d[v] = d[u] + w[i];
                    q.push(make_pair(-d[v], v));
                }
            }
        }
    }
} G;

struct edges {
    int u, v, h, w; //h 海拔；w 长度
} edge[M];
bool cmp(edges a, edges b) {
    if (a.h != b.h) return a.h > b.h;
    return a.w > b.w;
}

int n1 = 0;
struct Tree {
    int h[N], e[M], ne[M], idx = 0;
    int dep[N];
    int w[N];   //表示海拔，点权
    int Min[N]; //子树内最小的到 1 距离
    void init() {
        for (int i = 1; i <= n * 2; i++) h[i] = -1, dep[i] = 0;
        idx = 0;
    }
    void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
    int fa[N][25];
    void dfs(int u, int father) {
        fa[u][0] = father, dep[u] = dep[father] + 1;
        if (u <= n) Min[u] = G.d[u];
        else Min[u] = INF;
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (v == father) continue;
            dfs(v, u);
            Min[u] = min(Min[u], Min[v]);
        }
    }
    void get() {
        for (int i = 1; i <= 20; i++)
            for (int j = 1; j <= n * 2; j++) fa[j][i] = fa[fa[j][i - 1]][i - 1];
    }
} tr;

int p[N], q, k, s;
int find(int x) {
    return (p[x] == x) ? x : ( p[x] = find(p[x]) );
}

void solve() {
    scanf("%d%d", &n, &m);
    lst = 0, G.init(), tr.init();
    for (int i = 1, u, v, W, H; i <= m; i++) {
        scanf("%d%d%d%d", &u, &v, &W, &H);
        edge[i].u = u, edge[i].v = v, edge[i].w = W, edge[i].h = H;
        G.add(u, v, W), G.add(v, u, W);
    }
    G.dijkstra();


    sort(edge + 1, edge + 1 + m, cmp);
    for (int i = 1; i <= n * 2; i++) p[i] = i;
    n1 = n;

    for (int i = 1; i <= m; i++) {
        int u = edge[i].u, v = edge[i].v;
        int fu = find(u), fv = find(v);
        if (fu == fv) continue;
        n1++;
        tr.w[n1] = edge[i].h;
        tr.add(n1, fu), tr.add(fu, n1);
        tr.add(n1, fv), tr.add(fv, n1);
        p[fu] = n1, p[fv] = n1;
    }
    tr.dfs(n1, 0);
    tr.get();

    scanf("%d%d%d", &q, &k, &s);
    while (q--) {
        int v_0 = 0, p_0 = 0;
        scanf("%d%d", &v_0, &p_0);
        int v = (v_0 + k * lst - 1) % n + 1;
        int lim = (p_0 + k * lst) % (s + 1);
        for (int i = 20; i >= 0; i--) {
            if (tr.dep[v] <= (1 << i)) continue;
            int f = tr.fa[v][i];
            if (tr.w[f] > lim) v = f;
        }
        // printf("\t%d\n", v);
        printf("%d\n", lst = tr.Min[v]);
    }
}

int main() {
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}