rt，第四个样例没过，#7~#20 WA，求调！！！

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 8e5 + 5;
int t, k, s, n, m, q, nn, h[N], fa[N], dp[N][21], dep[N], dis[N], ans[N], lastans;
bool vis[N];
struct Node
{
	int x, y, w, h;
	bool operator < (const Node &b) const
	{
		return h > b.h;
	}
}a[N];
struct node
{
	int y, w;
};
vector<node> e[N];
vector<int> g[N];
void dijkstra(int s)
{
	memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
	priority_queue< pair<int, int> > pq;
	pq.push(make_pair(0, s));
	dis[s] = 0;
	while(!pq.empty())
	{
		int x = pq.top().second;
		pq.pop();
		if(vis[x])
			continue;
		vis[x] = true;
		for(auto i : e[x])
		{
			int y = i.y, w = i.w;
			if(dis[x] + w < dis[y])
			{
				dis[y] = dis[x] + w;
				pq.push(make_pair(-dis[y], y));
			}
		}
	}
	return;
}
int find(int x)
{
	if(fa[x] == x)
		return x;
	return fa[x] = find(fa[x]);
}
void kruskal()
{
	sort(a + 1, a + 1 + m);
	for(int i = 1; i <= n; i++)
		fa[i] = i;
	for(int i = 1; i <= m; i++)
	{
		int fx = find(a[i].x), fy = find(a[i].y);
		if(fx != fy)
		{
            n++;
			fa[fx] = fa[fy] = fa[n] = n;
            h[n] = a[i].h;
			g[n].push_back(fx);
			g[n].push_back(fy);
		}
	}
	return;
}
void init_ans(int x)
{
    ans[x] = dis[x];
    for(auto y : g[x])
    {
        init_ans(y);
        ans[x] = min(ans[x], ans[y]);
    }
    return;
}
void pre_lca(int x, int f)
{
    dep[x] = dep[f] + 1;
    dp[x][0] = f;
    for(int i = 1; (1 << i) <= dep[x]; i++)
        dp[x][i] = dp[dp[x][i - 1]][i - 1];
    for(auto y : g[x])
        pre_lca(y, x);
    return;
}
int query(int x, int p)
{
	for(int i = 23; i >= 0; i--)
		if(dp[x][i] && h[dp[x][i]] > p)
			x = dp[x][i];
	return ans[x];
}
void init()
{
    for(int i = 1; i <= n + m; i++)
        e[i].clear(), g[i].clear();
    memset(ans, 0x3f, sizeof(ans));
    memset(dp, 0, sizeof(dp));
    memset(h, 0xcf, sizeof(h));
    lastans = 0;
    return;
}
void solve()
{
	cin >> n >> m;
    nn = n;
    init();
	for(int i = 1; i <= m; i++)
	{
		cin >> a[i].x >> a[i].y >> a[i].w >> a[i].h;
		e[a[i].x].push_back((node){a[i].y, a[i].w});
		e[a[i].y].push_back((node){a[i].x, a[i].w}); 
	}
	dijkstra(1);
	kruskal();
    init_ans(n);
    pre_lca(n, 0);
	cin >> q >> k >> s;
	for(int i = 1; i <= q; i++)
	{
		int v, p;
        cin >> v >> p;
        v = (v + k * lastans - 1) % nn + 1;
        p = (p + k * lastans) % (s + 1);
        lastans = query(v, p);
        cout << lastans << "\n";
	}
    return;
}
signed main()
{
	cin >> t;
	while(t--)
		solve();
	return 0;
}