#include <bits/stdc++.h>
using namespace std;
struct node {
	long long u, v, w, h;
}a[4000000 + 10];
struct com {
	long long name, val;
	friend bool operator < (com x, com y) {
		return x.val < y.val;
	}
};
priority_queue <com> q;
com dis[2000000 + 10];
bool vis[2000000 + 10];
long long  cnt = 0, fa[2000000 + 10], anc[30][2000000 + 10];
long long last[2000000 + 10], n, m, kal[2000000 + 10]; 
vector <pair<long long , long long> > head[8000000 + 10];
long long inline found(long long x) {
	while (fa[x] != x)
		x = fa[x] = fa[fa[x]];
	return x;
}
void inline add (long long x, long long y, long long z) {
	head[x].push_back(make_pair(y, z));
}
void inline add2 (long long i, long long x, long long y) {
	x = found(x); y = found(y); cnt ++;
	fa[x] = fa[y] = fa[cnt] = cnt;
	kal[cnt] = a[i].h;
	add(cnt, x, 0); add(cnt, y, 0);
}
void inline best (long long x) {
	long long len = head[x].size();  last[x] = dis[x].val;
	if(x <= n) return ;
	for(register int i = 0; i < len; i ++) {
		long long f = head[x][i].first;
		anc[f][0] = x;  best(f);
		last[x] = min(last[x], last[f]);
	}
}
bool cmp (node x, node y) {return x.h > y.h;}
int main ()  {
 	long long T, lastans = 0; scanf ("%lld" ,&T);
	while (T --) {
		memset(last, 0, sizeof(last));
		memset(vis, false, sizeof(vis));
		memset(dis, 0x3f, sizeof(dis));
		scanf("%lld%lld", &n, &m);
		for ( register int i = 1; i <= m; i ++)  {
			scanf("%lld%lld%lld%lld", &a[i].u, &a[i].v, &a[i].w, &a[i].h);
			add(a[i].u, a[i].v, i); add(a[i].v, a[i].u, i);
		}
		long long len = head[1].size(); dis[1].val = 0; vis[1] = true;
		for(register int i = 1; i <= n; i ++) dis[i].name = i;
		for(register int i = 0; i < len; i ++) {
			long long  x = head[1][i].first, y = head[1][i].second;
			dis[x].val = a[y].w; q.push(dis[a[y].v]);
		}
		printf("\n");
		while(!q.empty()) { //cout<<1;
			com top = q.top();
			if(vis[top.name] || dis[top.name].val != top.val)
				{q.pop(); continue;}
			len = head[top.name].size(); vis[top.name] = true;
			for(register int i = 0 ; i < len; i ++) {
				long long x = head[top.name][i].first, y = head[top.name][i].second;
				if(dis[x].val > dis[top.name].val + a[y].w) {
					dis[x].val = dis[top.name].val + a[y].w;
					if(!vis[x])  q.push(dis[x]);
				}
			}
		} 
	
		sort(a + 1, a + m + 1, cmp); cnt = n;
		for(register int i = 1; i <= n + m; i ++) fa[i] = i;
		for(register int i = 1; i <= m; i ++)
			if(found(a[i].u) != found(a[i].v))
				add2(i, a[i].u, a[i].v);
		best(cnt);
//		for(register int i=  1; i <= cnt; i ++)
//			cout<<last[i]<<endl;
		for(register int i = 1; (1 << i) <= cnt; i ++)
			for(register int j = 1; j <= cnt ; j++)
				anc[j][i] = anc[anc[j][i -1]][i-1];
		long long Q, K, S; scanf("%lld%lld%lld", &Q, &K, &S);
		for(register int i = 1 ; i <= Q; i ++) {
			long long v0, p0; scanf("%lld%lld", &v0, &p0);
			v0 = (v0 + K * lastans - 1) % n + 1;
			p0 = (p0 + K * lastans) % (S + 1);
			for(register int j = 22; j >= 0; j --)
				if(anc[v0][j] && kal[anc[v0][j]] > p0)
					v0 = anc[v0][j];
//			cout<<v0<<endl;
			printf("%lld\n", last[v0]); lastans = last[v0];
		}
	}
}

RT 以上是代码，求大佬解答