#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
const int N = 2e5 + 7;
const int M = 4e5 + 7;
const int J = 20;
int logn[N << 1];
int T;
int n, m;
int last;
//Graph
class edge {
	public:
		int u;
		int v;
		int l;
		int a;
		friend bool operator > (edge x, edge y) {
			return x.a > y.a;
		}
};
edge e[M];
int cnt;
int head[N], nex[M << 1], to[M << 1], len[M << 1];
inline void add(int u, int v, int l, int a) {
	nex[++cnt] = head[u];
	to[cnt] = v;
	len[cnt] = l;
	head[u] = cnt;
}
//Shortest Path
class S {
	public:
		int d;
		int u;
		friend bool operator > (S a, S b) {
			return a.d > b.d;
		}
};
int mi[N << 1];
bool vis[N];
inline void dijkstra() {
	std::memset(vis + 1, false, n * sizeof(bool));
	std::memset(mi + 1, 0x3f, n * sizeof(int));
	std::priority_queue <S, std::vector <S>, std::greater <S> > heap;
	mi[1] = 0;
	heap.push((S){0, 1});
	while(!heap.empty()) {
		S c = heap.top();
		heap.pop();
		if(vis[c.u]) continue;
		vis[c.u] = true;
		for(int i = head[c.u]; i; i = nex[i]) {
			int v = to[i];
			if(vis[v]) continue;
			int w = len[i];
			if(mi[v] > mi[c.u] + w) {
				mi[v] = mi[c.u] + w;
				heap.push({mi[v], v});
			}
		}
	}
}
//Kruskal
int lch[N << 1], rch[N << 1], fas[N << 1], wei[N << 1];
int idx;
inline void init() {
	for(int i = 1; i <= n * 2 - 1; i++)
		fas[i] = i;
}
int find(int x) {
	return x == fas[x] ? x : (fas[x] = find(fas[x]));
}
inline void kruskal() {
	int tot = 0;
	idx = n;
	std::sort(e + 1, e + 1 + m, std::greater<edge>());
	for(int i = 1; i <= m; i++) {
		int u = e[i].u;
		int v = e[i].v;
		u = find(u);
		v = find(v);
		if(u != v) {
			idx++;
			fas[u] = idx;
			fas[v] = idx;
			lch[idx] = u;
			rch[idx] = v;
			wei[idx] = e[i].a;
			mi[idx] = std::min(mi[u], mi[v]);
		}
	}
}
//Binary Lift
int fa[J][N << 1];
int dep[N << 1];
void dfs(int u, int f) {
	fa[0][u] = f;
	dep[u] = dep[f] + 1;
	for(int i = 1; i <= logn[dep[u]]; i++)
		fa[i][u] = fa[i - 1][fa[i - 1][u]];
	if(lch[u] != 0) dfs(lch[u], u);
	if(rch[u] != 0) dfs(rch[u], u);
}
inline int cal(int u, int w) {
	for(int i = logn[dep[u]]; i >= 0; i--)
		if(wei[fa[i][u]] > w) u = fa[i][u];
	return mi[u];
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
//	std::freopen("test.in", "r", stdin);
//	std::freopen("test.out", "w", stdout);
	logn[1] = 0;
	for(int i = 2; i < N << 1; i++)
		logn[i] = logn[i / 2] + 1;
	std::cin >> T;
	for(int i = 0; i < T; i++) {
		last = 0;
		std::cin >> n >> m;
		cnt = 0;
		for(int j = 1; j <= m; j++) {
			int u, v, l, a;
			std::cin >> u >> v >> l >> a;
			add(u, v, l, a);
			add(v, u, l, a);
			e[j] = (edge){u, v, l, a};
		}
		dijkstra();
		init();
		kruskal();
		dfs(idx, 0);
		int q, k, s;
		std::cin >> q >> k >> s;
		for(int j = 0; j < q; j++) {
			int vv, pp, v, p;
			std::cin >> vv >> pp;
			v = (vv + k * last - 1) % n + 1;
			p = (pp + k * last) % (s + 1);
			std::cout << (last = cal(v, p)) << '\n';
		}
		std::memset(head + 1, 0, n * sizeof(int));
		std::memset(to + 1, 0, (m << 1) * sizeof(int));
		std::memset(nex + 1, 0, (m << 1) * sizeof(int));
		std::memset(lch, 0, n * 2 * sizeof(int));
		std::memset(rch, 0, n * 2 * sizeof(int));
	}
	return 0;
}

#11 Wrong Answer.wrong answer On line 236744 column 1, read 0, expected 5.