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

const int N = 1e6+7;

int n, m;

int q, K, s;

struct Edge{
	int u, v, l, a;
}edge[N];

struct Node{
	int v, w;
};

vector<int> G[N];
vector<Node> graph[N];

int fa[N];

int cnt;

ll min_dis[N];
ll dis[N];

int find(int x){
	while(fa[x] ^ x)
		x = fa[x] = fa[fa[x]];

	return x;
}

int deep[N];
int pre[N][50];

int c[N];

bool vis[N];

ll ans;

void getdeep(int u, int p){
	deep[u] = deep[p] + 1;

	pre[u][0] = p;

	for(int i(1); (1<<i) <= deep[u]; ++i)
		pre[u][i] = pre[pre[u][i-1]][i-1];

	for(int v : G[u])
		if(v ^ p)
			getdeep(v, u);

	return ;
}

int lca(int u, int v){
	if(deep[u] ^ deep[v]){
		if(deep[u] < deep[v])
			swap(u, v);

		int d = deep[u] - deep[v];

		for(int i(0); i <= 30; ++i)
			if((d>>i) & 1)
				u = pre[u][i];
	}

	if(u == v)
		return u;

	for(int i(30); i >= 0; --i)
		if(deep[pre[v][i]] > 0 && deep[pre[u][i]] > 0 && pre[u][i] ^ pre[v][i])
			u = pre[u][i], v = pre[v][i];

	return pre[u][0];
}
 
void kruskalrebuild(){
	cnt = n;

	for(int i(1); i <= n; ++i){
		fa[i] = i;
		min_dis[i] = dis[i];
		c[i] = 0;
	}

	sort(edge+1, edge+1+m, [](Edge x, Edge y){
		return x.a > y.a;
	});

	for(int i(1); i <= m; ++i){
		int x = find(edge[i].u);
		int y = find(edge[i].v);

		if(x == y)
			continue;

		fa[x] = fa[y] = ++cnt;
		fa[cnt] = cnt;
		c[cnt] = edge[i].a;

		G[cnt].emplace_back(x);
		G[cnt].emplace_back(y);

		min_dis[cnt] = min(min_dis[x], min_dis[y]);
	}
}

inline void changev(int &x){
	x = (x + K * ans - 1) % n + 1;
}

inline void changep(int &x){
	x = (x + K * ans) % (s + 1);
}

void dijkstra(){
	priority_queue<pair<ll, int>, vector<pair<ll, int> >, 
		greater<pair<ll, int> > > pq;

	for(int i(1); i <= n; ++i)
		dis[i] = 1e18;
	dis[1] = 0;

	pq.emplace(0, 1);

	while(!pq.empty()){
		auto tmp = pq.top();
		pq.pop();

		ll d = tmp.first;
		int u = tmp.second;

		if(d != dis[u])
			continue;

		for(auto e : graph[u])
			if(dis[e.v] > dis[u] + e.w)
				dis[e.v] = dis[u] + e.w,
				pq.emplace(dis[e.v], e.v);


	}
}

void Sol(){
	cin >> n >> m;

	cnt = 0;
	for(int i(1); i <= n; ++i){
		vector<Node>().swap(graph[i]);
    	vector<int>().swap(G[i]); 
	}

	for(int i(1), u, v, l, a; i <= m; ++i){
		cin >> u >> v >> l >> a;
		edge[i] = {u, v, l, a};

		graph[u].emplace_back(Node{v, l});
		graph[v].emplace_back(Node{u, l});
	}

	dijkstra();

	kruskalrebuild();

	getdeep(cnt, 0);

	cin >> q >> K >> s;

	while(q--){
		int v, p;
		cin >> v >> p;

		changev(v);
		changep(p);
		vis[v] = true;

		for(int i(30); i >= 0; --i){
			int tmp = pre[v][i];

			if(tmp != 0 && c[tmp] > p)
				v = tmp;
		}

		cout << min_dis[v] << '\n';
		ans = min_dis[v];
	}
}

int main(){
	cin.tie(0) -> ios::sync_with_stdio(false);

	int T;
	cin >> T;

	while(T--)
		Sol();

	return 0;
}