#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int x = 0 ,f = 1;
	char ch = getchar();
	while('0' > ch || ch > '9') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch & 15);
		ch = getchar();
	}
	return x * f;
}
const int N = 8e5 + 5;
struct Point {
	int from ,to ,l ,a;
	bool operator <(const Point &p) const {
		return a > p.a;
	}
}at[N];
vector<pair<int ,int > > vt[N];
int T ,n ,m ,Q ,K ,S ,u ,p ,fa[N][30] ,_fa[N] ,dist[N] ,dis[N][30];
bool vis[N];
priority_queue<pair<int ,int> ,vector<pair<int ,int> > ,greater<pair<int ,int> > > que;
void dijkstra() {
	memset(dist ,0x3f ,sizeof dist);
	memset(vis ,0 ,sizeof vis);
	while(!que.empty()) que.pop();
	que.push(make_pair(0 ,1));
	dist[1] = 0ll;
	while(!que.empty()) {
		pair<int ,int> tp = que.top();
		que.pop();
		if(vis[tp.second]) continue;
		vis[tp.second] = true;
		for(auto i:vt[tp.second]) {
			if(dist[i.first] > dist[tp.second] + i.second) {
				dist[i.first] = dist[tp.second] + i.second;
				que.push(make_pair(dist[i.first] ,i.first));
			}
		}
	}
	return ;
}
void dfs(register int t1 ,register int t2) {
	stack<pair<int ,int> > stk;
	stk.push(make_pair(t1 ,t2));
	while(!stk.empty()) {
		int u = stk.top().first ,father = stk.top().second;
		stk.pop();
		fa[u][0] = father;
		for(register int i = 1;i <= 20;++ i) {fa[u][i] = fa[fa[u][i - 1]][i - 1];dis[u][i] = min(dis[u][i - 1] ,dis[fa[u][i - 1]][i - 1]);}
		for(register auto i:vt[u]) {
			if(i.first == father) continue;
			dis[i.first][0] = i.second;
			stk.push(make_pair(i.first ,u));
		}
	}
	return ;
}
int get_father(int u ,int p) {
	for(register int i = 20;i >= 0;-- i) {if(dis[u][i] > p && fa[u][i] != 0)u = fa[u][i];}
	return u;
}
int find(int u) {
	if(u == _fa[u])return u;
	else return (_fa[u] = find(_fa[u]));
}
void solve() {
	memset(dis ,0x3f ,sizeof dis);
	memset(fa ,0 ,sizeof fa);
	n = read() ,m = read();
	int lastans = 0 ,cnt = 0;
	for(register int i = 1;i <= n;++ i) _fa[i] = i;
	for(register int i = 1;i <= n;++ i) vt[i].clear();
	for(register int i = 1 ,u ,v ,l ,a;i <= m;++ i) {
		u = read() ,v = read() ,l = read() ,a = read();
		at[i] = Point{u ,v ,l ,a};
		vt[at[i].from].push_back(make_pair(at[i].to ,at[i].l));
		vt[at[i].to].push_back(make_pair(at[i].from ,at[i].l));
	}
	dijkstra();
	for(register int i = 1;i <= n;++ i) vt[i].clear();
	sort(at + 1 ,at + m + 1);
	for(register int i = 1;i <= m;++ i) {
		int la = find(at[i].from) ,lb = find(at[i].to);
		if(la == lb) continue;
		_fa[la] = lb;
		vt[at[i].from].push_back(make_pair(at[i].to ,at[i].a));
		vt[at[i].to].push_back(make_pair(at[i].from ,at[i].a));
		if(++ cnt == n - 1) break; 
	}
	dis[1][0] = 0x3f3f3f3f;
	dfs(1 ,0);
	Q = read() ,K = read() ,S = read();
	for(register int i = 1;i <= Q;++ i) {
		u = (read() + K * lastans - 1) % n + 1;
		p = (read() + K * lastans) % (S + 1);
		u = get_father(u ,p);
		if(u == 0) u = 1;
		cout << dist[u] << '\n';
		lastans = dist[u];
	}
	return ;
}
signed main() {
//	freopen(".in" ,"r" ,stdin);
//	freopen(".out" ,"w" ,stdout);
	T = read();
	while(T --) solve();
	return 0;
}