#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 400005;

struct p{
	int u, v, w;
} b[N];

int t, n, m, pos, dw[N], dep[N];
vector<int> vc[N];

/*Dijkstra*/

struct P{
	int u;
	ll w;
};
vector<P> vec[N];

ll dis[N];
bool f[N];

struct pqz{
	int id;
	ll dis;
	bool operator < (const pqz &a) const{
		return a.dis < dis;
	}
};

void Dijkstra(int s){
	memset(dis, 0x3f, sizeof(dis));
	memset(f, 0, sizeof(f));
	priority_queue<pqz> pq;
	pq.push({s, 0});
	dis[s] = 0;
	while(!pq.empty()){
		int x = pq.top().id;
		pq.pop();
		if(f[x]) continue;
		f[x] = 1;
		for(int i = 0; i < vec[x].size(); i++){
			int u = vec[x][i].u, w = vec[x][i].w;
			if(dis[u] > dis[x] + w){
				dis[u] = dis[x] + w;
				pq.push({u, dis[u]});
			}
		}
	}
}

/*Kruskal*/

int F[N], pa[N][25];

int findf(int x){
	if(F[x] == x) return x;
	return F[x] = findf(F[x]);
}

bool cmp(p x, p y){
	return x.w > y.w;
}

void Kruskal(){
	int c = 0;
	sort(b + 1, b + m + 1, cmp);
	for(int i = 1; i <= m; i++){
		int u = b[i].u, v = b[i].v, w = b[i].w;
		int fx = findf(u), fy = findf(v);
		if(fx == fy) continue;
		c++;
		dw[++pos] = w;
		F[fx] = F[fy] = pos;
		vc[pos].push_back(fx);
		vc[pos].push_back(fy);
		if(c == n - 1) return;
	}
}

/*倍增*/

void dfs(int x, int fa){
	pa[x][0] = fa;
	dep[x] = dep[fa] + 1;
	for(int i = 0; i < vc[x].size(); i++){
		int v = vc[x][i];
		if(v != fa){
			dfs(v, x);
			dis[x] = min(dis[v], dis[x]);
		}
	}
}

void painit(){
	for(int i = 1; i <= pos; i++){
		for(int j = 1; j <= 20; j++){
			pa[i][j] = pa[pa[i][j - 1]][j - 1];
		}
	}
}

int findl(int x, int h){
	for(int i = 20; i >= 0; i--){
		if(dw[pa[x][i]] > h) x = pa[x][i];
	}
	return x;
}

/*--------------------------------------------*/

int main(){
	cin >> t;
	while(t--){
		cin >> n >> m;
		
		memset(pa, 0, sizeof(pa));
		for(int i = 1; i <= 2 * n; i++){
			F[i] = i;
			dw[i] = 0;
			vc[i].clear();
			vec[i].clear();
		}
		
		for(int i = 1; i <= m; i++){
			int u, v, l, a;
			cin >> u >> v >> l >> a;
			b[i] = {u, v, a};
			vec[u].push_back({v, l});
			vec[v].push_back({u, l});
		}
		
		Dijkstra(1);
		
		pos = n;
		Kruskal();
		
		dep[0] = 0;
		dfs(pos, 0);
		
		painit();
		
		int q, k, s, lsta = 0;
		cin >> q >> k >> s;
		
		while(q--){
			int v, p;
			cin >> v >> p;
			v = (v + k * lsta - 1) % n + 1;
			p = (p + k * lsta) % (s + 1);
			int lst = findl(v, p);
			lsta = dis[lst];
			cout << dis[lst] << '\n';
		}
	}
	return 0;
}