// This code is AI-generated. (AI 生成的代码)
// NOI2018 归程: Dijkstra from 1 for walking distances; Kruskal reconstruction
// tree over edges sorted by altitude (descending); binary lifting finds the
// highest ancestor with altitude > p, whose subtree min dist is the answer.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
enum { MAXN = 200005, MAXM = 400005, LOG = 19 };
struct Edge { int u, v, l, a; } E[MAXM];
static bool cmpA(const Edge &x, const Edge &y) { return x.a > y.a; }
static int hd[MAXN], nx[2 * MAXM], to[2 * MAXM], wt[2 * MAXM], ec;
static ll dist[MAXN];
static int fa[2 * MAXN], lc[2 * MAXN], rc[2 * MAXN], alt[2 * MAXN];
static int up[LOG][2 * MAXN];
static ll mind[2 * MAXN];
static int heap_node[2 * MAXM];
static ll heap_key[2 * MAXM];
static int hn;
static void hpush(int u, ll key) {
int i = hn++;
while (i) { int p = (i - 1) >> 1; if (heap_key[p] <= key) break; heap_key[i] = heap_key[p]; heap_node[i] = heap_node[p]; i = p; }
heap_key[i] = key; heap_node[i] = u;
}
static int hpop(ll &key) {
int r = heap_node[0]; key = heap_key[0];
int n = --hn; ll lk = heap_key[n]; int lu = heap_node[n];
int i = 0;
for (;;) {
int l = 2 * i + 1, rr = l + 1, m = i;
if (l < hn && heap_key[l] < (m == i ? lk : heap_key[m])) m = l;
if (rr < hn && heap_key[rr] < (m == i ? lk : heap_key[m])) m = rr;
if (m == i) break;
heap_key[i] = heap_key[m]; heap_node[i] = heap_node[m]; i = m;
}
heap_key[i] = lk; heap_node[i] = lu;
return r;
}
static int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; } return x; }
static char ib[1 << 24], ob[1 << 23];
static char *gp, *op;
static inline int rd() { while (*gp < '0') gp++; int v = 0; while (*gp >= '0' && *gp <= '9') v = v * 10 + (*gp++ - '0'); return v; }
static inline void wr(ll v) {
if (v < 0) { *op++ = '-'; v = -v; }
char t[24]; int k = 0;
if (!v) t[k++] = '0';
while (v) { t[k++] = (char)('0' + v % 10); v /= 10; }
while (k) *op++ = t[--k];
*op++ = '\n';
}
int main() {
int len = (int)fread(ib, 1, sizeof(ib) - 1, stdin);
ib[len] = 0; gp = ib; op = ob;
const ll INF = (ll)4e18;
int T = rd();
while (T--) {
int n = rd(), m = rd();
for (int i = 1; i <= n; i++) hd[i] = 0;
ec = 0;
for (int i = 0; i < m; i++) {
int u = rd(), v = rd(), l = rd(), a = rd();
E[i] = Edge{u, v, l, a};
to[++ec] = v; wt[ec] = l; nx[ec] = hd[u]; hd[u] = ec;
to[++ec] = u; wt[ec] = l; nx[ec] = hd[v]; hd[v] = ec;
}
for (int i = 1; i <= n; i++) dist[i] = INF;
hn = 0; dist[1] = 0; hpush(1, 0);
while (hn) {
ll key; int u = hpop(key);
if (key > dist[u]) continue;
for (int e = hd[u]; e; e = nx[e]) {
int v = to[e]; ll nd = key + wt[e];
if (nd < dist[v]) { dist[v] = nd; hpush(v, nd); }
}
}
sort(E, E + m, cmpA);
int cnt = n;
for (int i = 1; i <= n; i++) { fa[i] = i; alt[i] = 1 << 30; }
for (int i = 0; i < m; i++) {
int ru = find(E[i].u), rv = find(E[i].v);
if (ru == rv) continue;
int nd = ++cnt;
fa[nd] = nd; alt[nd] = E[i].a;
lc[nd] = ru; rc[nd] = rv;
up[0][ru] = nd; up[0][rv] = nd;
fa[ru] = nd; fa[rv] = nd;
}
for (int v = 1; v <= cnt; v++) if (!up[0][v]) up[0][v] = 0;
for (int k = 1; k < LOG; k++)
for (int v = 1; v <= cnt; v++) up[k][v] = up[k - 1][up[k - 1][v]];
for (int v = 1; v <= n; v++) mind[v] = dist[v];
for (int v = n + 1; v <= cnt; v++) {
ll a = mind[lc[v]], b = mind[rc[v]];
mind[v] = a < b ? a : b;
}
int Q = rd(), K = rd(), S = rd();
ll last = 0;
while (Q--) {
int v = rd(), p = rd();
v = (int)((v + last * K - 1 + (ll)n * K) % n + 1);
p = (int)((p + last * K) % (S + 1));
int x = v;
for (int k = LOG - 1; k >= 0; k--) {
int anc = up[k][x];
if (anc && alt[anc] > p) x = anc;
}
last = mind[x];
wr(last);
}
}
fwrite(ob, 1, op - ob, stdout);
return 0;
}