TLE 10pts 求助

#include <bits/stdc++.h>
#define N 400005
#define i64 long long int
int t, n, m;
struct edge {
	int v, l, a;
	edge(void) {
		return;
	}
	edge(int x, int y, int z) {
		v = x, l = y, a = z;
		return;
	}
};
struct dij {
	int p;
	i64 w;
	dij(void) {
		return;
	}
	dij(int x, i64 y) {
		p = x, w = y;
		return;
	}
	bool operator<(const dij &x) const {
		return w > x.w;
	}
};
struct eg {
	int u, v, a;
	eg(void) {
		return;
	}
	eg(int x, int y, int z) {
		u = x, v = y, a = z;
		return;
	}
	bool operator<(const eg &x) const {
		return a < x.a;
	}
};
std::vector<edge> graph[N];
i64 dis[N<<1];
int vis[N];
std::priority_queue<dij> heap;
std::priority_queue<eg> kus;
int fa[N<<1], val[N<<1], cnt;
std::vector<int> g[N<<1];
int tr[N][30];
int mval[N<<1];
void dijkstra(int rt) {
	dis[rt] = 0;
	heap.push(dij(rt, 0));
	while(!heap.empty()) {
		dij pr = heap.top();
		heap.pop();
		int u = pr.p;
		if(vis[u])
			continue;
		vis[u] = 1;
		for(edge e : graph[u]) {
			int v = e.v, w = e.l;
			if(dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				heap.push(dij(v, dis[v]));
			}
		}
	}
	return;
}
int find(int x) {
	if(fa[x] == x)
		return x;
	fa[x] = find(fa[x]);
	return fa[x];
}
void merge(int a, int b, int w) {
	int _a = find(a), _b = find(b);
	if(_a == _b)
		return;
	++ cnt;
	fa[_a] = fa[_b] = cnt;
	val[cnt] = w;
	g[cnt].push_back(_a);
	g[cnt].push_back(_b);
	return;
}
void kruskal(void) {
	while(cnt < (n<<1) - 1) {
		eg e = kus.top();
		kus.pop();
		merge(e.u, e.v, e.a);
	}
	return;
}
void dfs(int now) {
	for(int e : g[now]) {
		tr[e][0] = now;
		for(int i = 1; i <= 20; ++ i) {
			tr[e][i] = tr[tr[e][i - 1]][i - 1];
			if(e > n)
				dfs(e);
			dis[now] = std::min(dis[now], dis[e]);
		}
	}
	return;
}
i64 solve(int now, int lin) {
	for(int i = 20; i >= 0; -- i) {
		if(val[tr[now][i]] > lin)
			now = tr[now][i];
	}
	return dis[now];
}
void go(void) {
	scanf("%d%d", &n, &m);
	cnt = n;
	for(int i = 1; i <= n; ++ i)
		graph[i].clear();
	for(int i = 1; i <= n<<1; ++ i)
		fa[i] = i;
	while(!kus.empty())
		kus.pop();
	for(int i = 1, u, v, l, a; i <= m; ++ i) {
		scanf("%d%d%d%d", &u, &v, &l, &a);
		graph[u].push_back(edge(v, l, a));
		graph[v].push_back(edge(u, l, a));
		kus.push(eg(u, v, a));
	}
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	memset(tr, 0, sizeof(tr));
	while(!heap.empty())
		heap.pop();
	dijkstra(1);
	kruskal();
	dfs(cnt);
	int q, k, s, v, p;
	i64 ans, lastans = 0;
	scanf("%d%d%d", &q, &k, &s);
	while(q --) {
		scanf("%d%d", &v, &p);
		v = (v + k * lastans - 1) % n + 1;
		p = (p + k * lastans) % (s + 1);
		ans = solve(v, p);
		printf("%lld\n", ans);
		lastans = ans;
	}
	return;
}
int main(void) {
	scanf("%d", &t);
	while(t --) {
		go();
	}
	return 0;
}