神秘MLE求助

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=998244353;
int n,m,_,la,z,Q,K,S,f[N],a[N],h[18][N];
bool vis[N];
long long d[N];
struct edge{
	int u,v,w,p;
	bool operator<(const edge&a)const{
		return p>a.p;
	}
}e[N]; 
vector<pair<int,int> > g[N];
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
priority_queue<pair<long long,int>> q;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	freopen("return5.in","r",stdin);
	freopen("return.out","w",stdout);
	cin>>_;
	while(_--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			f[i]=i,
			g[i].clear();
		for(int i=1;i<=m;i++)
			cin>>e[i].u>>e[i].v>>e[i].w>>e[i].p,
			g[e[i].u].push_back({e[i].v,e[i].w}),
			g[e[i].v].push_back({e[i].u,e[i].w});
		sort(e+1,e+1+m);
		z=n;
		for(int i=1;i<=m;i++){
			int u=find(e[i].u),v=find(e[i].v);
			if(u!=v)
				f[++z]=z,
				g[z].clear(),
				g[u].push_back({z,0}),
				g[v].push_back({z,0}),
				f[u]=f[v]=z,
				h[0][u]=h[0][v]=z,
				a[z]=e[i].p;
		}
		for(int i=1;i<=z;i++)
			vis[i]=0,
			d[i]=1e16;
		d[1]=0;
		q.push({0,1});
		while(!q.empty()){
			int u=q.top().second;
			q.pop();
			if(vis[u])
				continue;
			for(auto i:g[u]){
				int v=i.first,w=i.second;
				if(d[v]>d[u]+w)
					d[v]=d[u]+w,
					q.push({-d[v],v});
			}
		}
		for(int i=1;i<18;i++)
			for(int j=1;j<=z;j++)
				h[i][j]=h[i-1][h[i-1][j]];
		cin>>Q>>K>>S;
		la=0;
		while(Q--){
			int v,p;
			cin>>v>>p;
			v=(v+K*la-1)%n+1;
			p=(p+K*la)%(S+1);
			for(int i=17;i>=0;i--)
				if(a[h[i][v]]>p)
					v=h[i][v];
			cout<<d[v]<<'\n';
			la=d[v];
		}
	}
	return 0;
}