寄

#include<bits/stdc++.h>
using namespace std;
#define ll int
ll cnt=0,n,m,a,b,c,addedge,addpoint,f[500009][29],point[500009],deep[500009],x,y,T,Q,K,S;
ll dis[500009],aa,bb;
struct dijedge{
	ll 	to,val;
};
vector<ll>v1[500009];
vector<ll>v2[500009];
struct dijpoint{
	ll u,dis;
  	bool operator>(const dijpoint& a) const { return dis > a.dis; }
}tmp1,tmp2;
ll fa[500009],ans[500009];
struct node{
	ll to,val,start,a;
}e[500009];
ll find(ll x)	
{
	if(fa[x]==x)
	{
		return x;
	}
	return fa[x]=find(fa[x]);
}
bool cmp(node s1,node s2)
{
	return s1.a>s2.a; 
 } 
void add(ll x,ll y)
{
	v2[x].push_back(y);
	v2[y].push_back(x);
}
priority_queue<dijpoint, vector<dijpoint>, greater<dijpoint> > q;
void dij()
{
	memset(dis,0x3f,sizeof(dis));
	tmp1.u=1,tmp1.dis=0;
	q.push(tmp1);
	while(!q.empty())
	{	 
		tmp1=q.top();
		q.pop();
		if(dis[tmp1.u]<=tmp1.dis)
		{
			continue;
		}
		dis[tmp1.u]=tmp1.dis;
		for(ll i=0;i<v1[tmp1.u].size();i++)
		{
			if(e[v1[tmp1.u][i]].start==tmp1.u)
			{
				tmp2.u=e[v1[tmp1.u][i]].to;
			}
			else
			{
				tmp2.u=e[v1[tmp1.u][i]].start;
			}
			tmp2.dis=tmp1.dis+e[v1[tmp1.u][i]].val;
			if(dis[tmp2.u]<=tmp2.dis)
			{
				continue;
			}
			q.push(tmp2);
		}
	}
}
void init()
{
	addpoint=addedge=0;
	for(ll i=1;i<=200000;i++)
	{
		v1[i].clear();
		v2[i].clear();
	}
	memset(deep,0,sizeof(deep));
	memset(f,0,sizeof(f));
	memset(dis,0x3f,sizeof(dis));
	memset(e,0,sizeof(e));
	memset(ans,0x3f,sizeof(ans));
	while(!q.empty())
	{
		q.pop();
	}
}
void kruskal()
{
	ll lll=0;
	sort(e+1,e+m+1,cmp);
	for(ll i=1;i<=m&&lll<=n-1;i++)
	{
		ll q=find(e[i].start),w=find(e[i].to);
		if(q==w)	
		{
			continue;
		}
		lll++;
		addpoint++;
		point[addpoint]=e[i].a;
		add(addpoint,find(e[i].start));
		add(addpoint,find(e[i].to));
		fa[fa[e[i].start]]=fa[fa[e[i].to]]=addpoint;
	}
}
void dfs(ll x,ll father)
{	
	deep[x]=deep[father]+1;
	ans[x]=dis[x];
	for(ll i=0;i<v2[x].size();i++)
	{
		if(v2[x][i]==father)
		{
			continue;
		}
		f[v2[x][i]][0]=x;
		for(ll j=1;j<=18;j++)
		{
			f[v2[x][i]][j]=f[f[v2[x][i]][j-1]][j-1];
		}
		dfs(v2[x][i],x);
		ans[x]=min(ans[x],ans[v2[x][i]]);
	}
	return ;
}
ll ff(ll x,ll a)
{
	for(ll i=18;i>=0;i--)
	{
		if(point[f[x][i]]>a)
		{
			x=f[x][i];
		}
	}
	return ans[x];
}
int main()
{
	cin>>T;
	while(T--)
	{
		init();
		cin>>n>>m;
		addpoint=n,addedge=m;	
		for(ll i=1;i<=500000;i++)
		{
			fa[i]=i;
		}
		for(ll i=1;i<=m;i++)
		{
			cin>>e[i].start>>e[i].to>>e[i].val>>e[i].a;
			if(e[i].start==e[i].to)
			{
				i--;
				m--;	
			}
			else
			{
				v1[e[i].start].push_back(i);
				v1[e[i].to].push_back(i); 
			}
		}
		cin>>Q>>K>>S;
		dij(); 
		kruskal();
		dfs(find(1),0);	
		ll lastans=0;
		while(Q--)
		{
			cin>>aa>>bb;
			ll vv=(aa+K*lastans-1)%n+1;
			ll pp=(bb+K*lastans)%(S+1);
			lastans=ff(vv,pp);
			cout<<lastans<<endl;
		}
	}
	return 0;
 }