#include<bits/stdc++.h>
using namespace std;
namespace qwq{
	inline int read(){
		int n = 0;  
		int f = 1;
		char c = getchar();
		while(c < '0' || c > '9'){
			if(c == '-') f = -1;
			c = getchar();
		}
		while(c >= '0' && c <= '9'){
			n = (n << 3) + (n << 1) + (c ^ 48);
			c = getchar();
		}
		return n * f;
	}
	inline void Write(int x){
		if(x < 0){
			putchar('-');
			x = -x;
		}
		if(x > 9) Write(x / 10);
		putchar((x % 10) ^ 48);
		return;
	}
	inline void write(int x, char c){
		Write(x);
		putchar(c);
	}
}
using namespace qwq;
struct node{
	int val, hai, chang;
	bool operator > (const node &A)const{
		return chang > A.chang;
	}
};
struct edge{
	int a, b, hi;
	bool operator < (const edge &A)const{
		return hi > A.hi;
	}
} v1[1000010];
int n, m, T, Q, K, S, last, mi[1000010], dis[1000010], st[1000010], f[1000010], d[1000010], cnt, g[200010][110];
vector<node> v[1000010];
vector<int> e[1000010];
int find(int x){
	if(f[x] != x) return f[x] = find(f[x]);
	return x;
}
void dijkstra(){
	memset(dis, 0x7f, sizeof(dis));
	memset(st, 0, sizeof(st));
	priority_queue<node, vector<node>, greater<node> > q;
	dis[1] = 0;
	q.push(node{1, 0});
	while(!q.empty()){
		node f = q.top();
		q.pop();
		if(st[f.val]) continue;
		st[f.val] = true;
		for(int i = 0; i < v[f.val].size(); i++){
			if(dis[v[f.val][i].val] > dis[f.val] + v[f.val][i].chang){
				dis[v[f.val][i].val] = dis[f.val] + v[f.val][i].chang;
				q.push(node{v[f.val][i].val, dis[f.val] + v[f.val][i].chang});
			}
		}
	}
	return ;
}
void dfs(int u){
	mi[u] = dis[u];
	for(int i = 0; i < e[u].size(); i++){
		g[e[u][i]][0] = u;
		dfs(e[u][i]);
		mi[u] = min(mi[e[u][i]], mi[u]);
	}
}
void kruskal(){
	sort(v1+1, v1+m+1);
    for(int i = 1; i <= 2 * n; i++) f[i] = i;
    cnt = n;
    for(int i = 1; i <= m; i++){
        int a = find(v1[i].a), b = find(v1[i].b);
        if(a ^ b){
            d[++cnt] = v1[i].hi;
            f[b] = cnt;
			f[a] = f[b];
            e[cnt].push_back(a);
            e[cnt].push_back(b);
        }
    }
    dfs(cnt);
}
int main(){
	T = read();
	while(T--){
		last = 0;
		for(int i = 1; i <= 1000000; i++){
			v[i].clear();
			e[i].clear();
			v1[i].a = 0;
			v1[i].b = 0;
			v1[i].hi = 0;
		}
		memset(g, 0, sizeof(g));
		memset(d, 0, sizeof(d));
		memset(mi, 0, sizeof(mi));
		n = read(), m = read();
		for(int i = 1; i <= m; i++){
			int x, y, l, a;
			v1[i].a = read(), v1[i].b = read(), l = read(), v1[i].hi = read();
			x = v1[i].a, y = v1[i].b, a = v1[i].hi;
			v[x].push_back(node{y, a, l});
			v[y].push_back(node{x, a, l});
		}
		dijkstra();
		kruskal();
		for(long long i = 1; (1ll << i) <= cnt; i++){
			for(int j = 1; j <= cnt; j++){
				g[j][i] = g[g[j][i-1]][i-1];
			}
		}
		Q = read(), K = read(), S = read();
		while(Q--){
			int vi = read(), si = read();
			vi = (vi + K * last - 1) % n + 1;
			si = (si + K * last) % (S + 1);
			for(int i = 22; ~i; i--){
				if(g[vi][i] && d[g[vi][i]] > si){
					vi = g[vi][i];
				}
			}
			write(mi[vi], '\n');
			last = mi[vi];
		}
	}
	return 0;
}