#6 RE #11 WA #12 14 18 20 MLE #13 17 19 TLE

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
const int N = 2e5 + 7;
const int M = 4e5 + 7;
const int J = 30;
int T;
int n, m;
int q, k, s;
int last;
class edge {
	public:
		int tail;
		int head;
		int length;
		int height;
};
class S {
	public:
		int id;
		unsigned int dis;
		friend bool operator < (S x, S y) {
			return x.dis < y.dis;
		}
		friend bool operator > (S x, S y) {
			return x.dis > y.dis;
		}
};
edge e[M];
int temp;
int nex[M], head[N], len[M], hei[M], to[M];
int cnt;
int id;
bool vis[N];
int lch[N << 1], rch[N << 1];
int wei[N << 1];
unsigned int minleaf[N << 1];
int fas[N << 1];
int fak[J][N << 1], dep[N << 1];
int logn[N << 1];
int read() {
	char c = getchar();
	int res = 0;
	int f = 1;
	while(c < '0' || c > '9') {
		if(c == '-')
			f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = (res << 3) + (res << 1) + c - '0';
		c = getchar();
	}
	return res * f;
}
void write(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
bool greater_hei(edge x, edge y) {
	return x.height > y.height;
}
void add(int u, int v, int l, int a) { //链式前向星的加边 
	nex[++cnt] = head[u];
	to[cnt] = v;
	len[cnt] = l;
	hei[cnt] = a;
	head[u] = cnt;
}
void dijkstra() {
	std::memset(minleaf + 1, 0x3f, n * sizeof(int));
	std::memset(vis + 1, false, n * sizeof(bool));
	std::priority_queue <S, std::vector <S>, std::greater<S> > qu; 
	minleaf[1] = 0;
	qu.push((S){1, 0});
	while(!qu.empty()) {
		int u = qu.top().id;
		qu.pop();
		if(vis[u])
			continue;
		vis[u] = true;
		for(int i = head[u]; i; i = nex[i]) {
			int v = to[i];
			unsigned int w = len[i];
			if(minleaf[v] > minleaf[u] + w) {
				minleaf[v] = minleaf[u] + w;
				qu.push((S){v, minleaf[v]});
			}
		}
	}
}
int find(int x) {
	return x == fas[x] ? x : (fas[x] = find(fas[x]));
}
void kruskal() {
	std::sort(e, e + m, greater_hei);
	for(int i = 0; i < m; i++) {
		int u = e[i].tail;
		int v = e[i].head;
		int w = e[i].height;
		u = find(u);
		v = find(v);
		if(u != v) {
			id++;
			lch[id] = u;
			rch[id] = v;
			wei[id] = w;
			fas[u] = id;
			fas[v] = id;
			minleaf[id] = std::min(minleaf[u], minleaf[v]);
		}
	}
}
void init(int u, int f, int d) {
	dep[u] = dep[f] + 1;
	fak[0][u] = f;
	for(int i = 1; i <= logn[dep[u]]; i++)
		fak[i][u] = fak[i - 1][fak[i - 1][u]];
	if(lch[u] != 0) init(lch[u], u, d + 1);
	if(rch[u] != 0) init(rch[u], u, d + 1);
}
int cal(int v, int p) {
	for(int i = logn[dep[v]]; i >= 0; i--)
		if(wei[fak[i][v]] > p) v = fak[i][v]; 
	return minleaf[v];
}
int main() {
	//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; 
	T = read(); 
	while(T--) {
		temp = 0;
		cnt = 0;
		std::memset(nex + 1, 0, m * sizeof(int));
		std::memset(head + 1, 0, n * sizeof(int));
		std::memset(lch + 1, 0, (2 * n + 1) * sizeof(int));
		std::memset(rch + 1, 0, (2 * n + 1) * sizeof(int));
		dep[0] = 0;
		last = 0; 
		n = read();
		m = read();
		int u, v, l, a;
		for(int i = 0; i < m; i++) {
			u = read();
			v = read();
			l = read();
			a = read();
			e[temp++] = (edge){u, v, l, a};
			add(u, v, l, a);
			add(v, u, l, a);
		}
		for(int i = 1; i <= 2 * n + 1; i++)
			fas[i] = i;
		dijkstra();
		id = n;
		kruskal();
		init(id, 0, 0);
		std::cin >> q >> k >> s;
		for(int i = 0; i < q; i++) {
			int vv, pp, v, p;
			vv = read();
			pp = read();
			v = (vv + k * last - 1) % n + 1;
			p = (pp + k * last) % (s + 1);
			last = cal(v, p);
			write(last);
			putchar('\n');
		}
	}
	return 0;
}