//https://www.luogu.com.cn/problem/P4768
#include<unordered_map>
#include<functional>
#include<algorithm>
#include<iostream>
#include<cassert>
#include<cstring>
#include<numeric>
#include<bitset>
#include<random>
#include<cstdio>
#include<string>
#include<vector>
#include<ctime>
#include<stack>
#include<queue>
#include<cmath>
#include<set>
#include<map>

#define fi first
#define se second
#define int long long
#define pii pair<int,int>
#define NO cout << "NO\n";
#define YES cout << "YES\n";
#define stop system("pause");
#define debug printf("++ ++\n");
#define cout(a) cout << (#a) << " = " << a << endl;
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5;
random_device gen;
mt19937 rnd(gen());
int n, m, cur;
int dis[(N << 1) + 5], dep[(N << 1) + 5], a[(N << 1) + 5], fa[(N << 1) + 5][20 + 5];//到 1 节点的最短路, 深度 及 当前新建点所在边的海拔
vector<pii > G[N + 5];
vector<int> NG[(N << 1) + 5];
bitset < N + 5 > vis;

/* 终点是一切概率的结束，也是一切期望的开始 */
/* *
 * 可能做法: 基础算法(思维, 暴力, 贪心, 二分...) /  图论 / 数据结构
 * */


struct edge {
	int u, v, l, a;

	edge() {}

	edge(int u, int v, int l, int a) : u(u), v(v), l(l), a(a) {}

	friend bool operator<(edge a, edge b) {
		return a.a > b.a;
	}
};


struct DSU {
	std::vector<int> pre, sz;

	DSU(int n) : pre(n + 1), sz(n + 1, 1) {
		std::iota(pre.begin(), pre.end(), 0ll);
	}

	int find(int x) {
		return pre[x] == x ? x : pre[x] = find(pre[x]);
	}

	int size(int x) {
		return sz[find(x)];
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	bool merge(int x, int y) {
		int fx = find(x), fy = find(y);
		if (fx == fy) return false;
		if (sz[fx] > sz[fy]) swap(fx, fy);
		sz[fy] += sz[fx];
		pre[fx] = fy;
		return true;//合并成功
	}

};

void dijkstra(int root) {
	for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = false;
	priority_queue<pii, vector<pii >, greater<> > pq;
	dis[root] = 0;
	pq.push(make_pair(0ll, root));

	while (!pq.empty()) {
		auto [d, u] = pq.top();//引用在队列这种需要时刻 pop 的 STL 不要使用, 会出现意想不到的 BUG
		pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (auto [v, w] : G[u]) {
			int dist = d + w;
			if (dis[v] < dist) continue;
			dis[v] = dist;
			pq.push(make_pair(dist, v));
		}
	}
}

void dfs(int father, int u) {
//	assert(false);
//	cout(father);
//	cout(u);
	dep[u] = dep[father] + 1;
	fa[u][0] = father;
	//树上倍增
//	assert(u >= 0 && u <= N);
	for (int i = 1; i <= __lg(dep[u] - 1); i++) {
//		assert(i >= 0 && i <= 20);
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	for (auto v : NG[u]) {
		if (v == father) continue;
//		assert(v >= 1 && v <= N);
		dfs(u, v);
		dis[u] = min(dis[u], dis[v]);
	}
}

int solve(int root, int p) {
	for (int i = __lg(dep[root] - 1); i >= 0; i--) {
		int nex = fa[root][i];
		if (nex <= 0 || a[nex] <= p) continue;
		root = nex;
	}
	return dis[root];
}


void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) G[i].clear();
	for (int i = 1; i <= n << 1; i++) NG[i].clear();
	vector<edge> e;
	for (int i = 0; i < m; i++) {
		int u, v, l, a;
		cin >> u >> v >> l >> a;
		G[u].emplace_back(v, l);
		G[v].emplace_back(u, l);
		e.emplace_back(u, v, l, a);
	}

	dijkstra(1);

	DSU dsu = DSU(n << 1);
	//Kruskal 重构
	std::sort(e.begin(), e.end());
	cur = n;
	for (int i = 0; i < m; i++) {
		int u = e[i].u, v = e[i].v, lx = e[i].l, ax = e[i].a;
		//RE
		if (dsu.same(u, v)) continue;//已在同一连通块, 直接 continue

		int fu = dsu.find(u), fv = dsu.find(v);
		cur++;
		NG[cur].push_back(fu);//化边为点
		NG[cur].push_back(fv);//化边为点
		a[cur] = ax;
		//合并连通块, 注意指向
		dsu.pre[fu] = cur;
		dsu.pre[fv] = cur;
	}

	for (int i = n + 1; i <= cur; i++) dis[i] = INF;
	dfs(0, cur);
//	exit(0);

	int q, K, S, _root, _p, lastance = 0;
	cin >> q >> K >> S;
	for (int i = 1; i <= q; i++) {
		cin >> _root >> _p;
		int root = (_root + K * lastance - 1) % n + 1, p = (_p + K * lastance) % (S + 1);
//		cout << (lastance = solve(root, p)) << '\n';
		lastance = solve(root, p);
		cout << lastance << '\n';
	}
}

signed main() {
	std::ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	cin >> t;
	while (t--) solve();
	return 0;
}