#ifdef ONLINE_JUDGE
#define ___coding false
#else
#define ___coding true
#endif
#include<bits/stdc++.h>
#define UP(i,a,b) for(i=a;i<=(b);++i)
#define DN(i,a,b) for(i=a;i>=(b);--i)
#define up(i,a,b) for(i=a;i<(b);++i)
#define dn(i,a,b) for(i=a;i>(b);--i)
const int BUF_SIZE(1<<14);
typedef long long ll;typedef unsigned long long ull;typedef __int128 pll;bool ___f;char ___c,___a[45],*___p,___ibuf[BUF_SIZE+1],*___ib(___ibuf),*___ie(___ibuf),___obuf[BUF_SIZE+1],*___ob(___obuf),*___oe(___obuf+BUF_SIZE);inline char& gtch(){return ___ib==___ie&&(___ie=(___ib=___ibuf)+fread(___ibuf,1,BUF_SIZE,stdin),___ib==___ie)?*___ib=-1:*___ib++;}void ___flush(){fwrite(___obuf,1,___ob-___obuf,stdout);___ob=___obuf;}inline void ptch(char c){if(___ob==___oe)___flush();*___ob=c;++___ob;}void rd(bool &r){r=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch())r|=(___c!='0');}void rd(char &c){for(c=gtch();c==' '||c=='\r'||c=='\n';c=gtch());}inline void rd(int &r){r=___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch())___f=(___c=='-');for(;___c>='0'&&___c<='9';___c=gtch())r=(r<<3)+(r<<1)+(___c^'0');if(___f)r=~(r-1);}inline void rd(ll &r){r=___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch())___f=(___c=='-');for(;___c>='0'&&___c<='9';___c=gtch())r=(r<<3)+(r<<1)+(___c^'0');if(___f)r=~(r-1);}void rd(ull &r){r=0;for(___c=gtch();___c<'0'||___c>'9';___c=gtch());for(;___c>='0'&&___c<='9';___c=gtch())r=(r<<3)+(r<<1)+(___c^'0');}void rd(char *s){for(*s=gtch();*s==' '||*s=='\r'||*s=='\n';*s=gtch());for(;~*s&&*s!=' '&&*s!='\r'&&*s!='\n';++s,*s=gtch());*s=0;}void rd(pll &r){r=___f=false;for(___c=gtch();___c<'0'||___c>'9';___c=gtch())___f=(___c=='-');for(;___c>='0'&&___c<='9';___c=gtch())r=(r<<3)+(r<<1)+(___c^'0');if(___f)r=~(r-1);}void wt(char c){ptch(c);}inline void wt(int r){if(r==0)return ptch('0');if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){*++___p=char(r%10)^'0';r/=10;}while(___p!=___a)ptch(*___p--);}inline void wt(ll r){if(r==0)return ptch('0');if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){*++___p=char(r%10)^'0';r/=10;}while(___p!=___a)ptch(*___p--);}void wt(ull r){if(r==0)return ptch('0');___p=___a;while(r!=0){*++___p=char(r%10)^'0';r/=10;}while(___p!=___a)ptch(*___p--);}void wt(char* s){for(;*s;ptch(*s++));}inline void wt(const char* s){for(;*s;ptch(*s++));}void wt(pll r){if(r==0)return ptch('0');if(r<0){ptch('-');r=~(r-1);}___p=___a;while(r!=0){*++___p=char(r%10)^'0';r/=10;}while(___p!=___a)ptch(*___p--);}template<typename T,typename... P>inline void rd(T &a,P &...b){rd(a);rd(b...);}template<typename T,typename... P>inline void wt(T a,P ...b){wt(a);wt(b...);}template<typename T>void RD(T* a,int n){while(n--)rd(*a++);}template<typename T>T ___min(T &a,T &b){return a<b?a:b;}template<typename T,typename... P>T ___min(T &a,T &b,P &...c){return ___min(a,b=___min(b,c...));}template<typename T,typename... P>T min(T a,P ...b){return ___min(a,b...);}template<typename T>T ___max(T &a,T &b){return a>b?a:b;}template<typename T,typename... P>T ___max(T &a,T &b,P &...c){return ___max(a,b=___max(b,c...));}template<typename T,typename... P>T max(T a,P ...b){return ___max(a,b...);}
/*

*/
const ll INF(1e18);
int T,n,m,q,k,S;
ll last_ans;
struct edge_1{
	int u,v,w,a;
};
bool cmp(const edge_1 &u,const edge_1 &v){
	return u.a>v.a;
}
struct edge{
	int p,v,w;
	edge(){}
	edge(int &p,int &v,int &w):p(p),v(v),w(w){}
};
struct graph{
	int p;
	std::vector<int> h;
	std::vector<edge> e;
	void add(int u,int v,int w){
		e[p]=edge(h[u],v,w);
		h[u]=p++;
	}
	void init(){
		h.resize(n);
		e.resize(m<<1);
		for(std::vector<int>::iterator i=h.begin();i!=h.end();++i){
			*i=-1;
		}
		p=0;
	}
	void clear(){
		h.shrink_to_fit();
		e.shrink_to_fit();
	}
}g;
struct persistent_array_node{
	int ls,rs;
	ll vl;
	persistent_array_node():ls(0),rs(0),vl(0){}
};
std::vector<bool> vs;
std::vector<int> f,s,mnd;
std::vector<ll> ds;
std::vector<edge_1> ed;
std::vector<persistent_array_node> t;
int new_node(){
	t.push_back(persistent_array_node());
	return t.size()-1;
}
int update(int x,int k,int p,int l,int r){
	int mid((l+r)>>1),u(new_node()),tmp;
	if(l==r){
		t[u].vl=k;return u;
	}
	t[u]=t[p];
	if(x<=mid){
		tmp=update(x,k,t[p].ls,l,mid);t[u].ls=tmp;
	}else{
		tmp=update(x,k,t[p].rs,mid+1,r);t[u].rs=tmp;
	}
	return u;
}
int build(int l,int r,std::vector<ll>* a){
	int mid((l+r)>>1),u(new_node()),tmp;
	if(l==r){
		t[u].vl=a->at(l);
		return u;
	}
	tmp=build(l,mid,a);t[u].ls=tmp;
	tmp=build(mid+1,r,a);t[u].rs=tmp;
	return u;
}
int query(int u,int x,int l,int r){
	int mid((l+r)>>1);
	if(l==r){
		return t[u].vl;
	}
	if(x<=mid){
		return query(t[u].ls,x,l,mid);
	}else{
		return query(t[u].rs,x,mid+1,r);
	}
}
void travel(int u,int l,int r){
	int mid((l+r)>>1);
	if(l==r){
		printf("%lld%c",t[u].vl," \n"[l==n-1]);
		return;
	}
	travel(t[u].ls,l,mid);
	travel(t[u].rs,mid+1,r);
}
int fd(int ver,int k){
	int fa(query(f[ver],k,0,n-1));
	return fa==k?k:fd(ver,fa);
}
void merge(int u,int v,int ver){
	int su,sv,mnds;
	u=fd(ver-1,u);v=fd(ver-1,v);
	if(u!=v){
		su=query(s[ver-1],u,0,n-1);sv=query(s[ver-1],v,0,n-1);
		mnds=min(query(mnd[ver-1],u,0,n-1),query(mnd[ver-1],v,0,n-1));
		if(su>sv){
			std::swap(u,v);
			std::swap(su,sv);
		}
		f[ver]=update(u,v,f[ver-1],0,n-1);
		s[ver]=update(v,su+sv,s[ver-1],0,n-1);
		mnd[ver]=update(v,mnds,mnd[ver-1],0,n-1);
	}else{
		f[ver]=f[ver-1];
		s[ver]=s[ver-1];
		mnd[ver]=mnd[ver-1];
	}
}
void dijkstra(){
	int i,u,v,w;
	std::priority_queue<std::pair<ll,int>> p;
	vs.resize(n);
	for(std::vector<bool>::iterator i(vs.begin());i!=vs.end();++i){
		*i=false;
	}
	for(std::vector<ll>::iterator i(ds.begin());i!=ds.end();++i){
		*i=INF;
	}
	ds[0]=0;
	p.push(std::make_pair(0ll,0));
	while(p.size()){
		u=p.top().second;p.pop();
		if(!vs[u]){
			vs[u]=true;
			for(i=g.h[u];~i;i=g.e[i].p){
				v=g.e[i].v;w=g.e[i].w;
				if(ds[u]+w<ds[v]){
					ds[v]=ds[u]+w;
					if(!vs[v]){
						p.push(std::make_pair(-ds[v],v));
					}
				}
			}
		}
	}
	vs.shrink_to_fit();
}

void ___main(){
	int ca,i,v,p;
	rd(T);
	UP(ca,1,T){
		last_ans=0;
		rd(n,m);
		g.init();
		ed.resize(m);
		for(std::vector<edge_1>::iterator i(ed.begin());i!=ed.end();++i){
			rd(i->u,i->v,i->w,i->a);
			--i->u;--i->v;
			g.add(i->u,i->v,i->w);
			g.add(i->v,i->u,i->w);
		}
		std::sort(ed.begin(),ed.end(),cmp);
		f.resize(n+1);
		s.resize(n+1);
		mnd.resize(n+1);
		ds.resize(n);
		t.push_back(persistent_array_node());

		{
			std::vector<ll>::iterator i(ds.begin());
			int j(0);
			for(;i!=ds.end();++i,++j){
				*i=j;
			}
		}
		f[0]=build(0,n-1,&ds);

		for(std::vector<ll>::iterator i=ds.begin();i!=ds.end();++i){
			*i=1;
		}
		s[0]=build(0,n-1,&ds);

		dijkstra();
		g.clear();
		mnd[0]=build(0,n-1,&ds);

		ds.shrink_to_fit();

		{
			std::vector<edge_1>::iterator i(ed.begin());
			int j(1);
			for(;i!=ed.end();++i,++j){
				merge(i->u,i->v,j);
			}
		}
		ed.shrink_to_fit();
		
		rd(q,k,S);
		up(i,0,q){
			rd(v,p);
			v=(v+k*last_ans-1)%n+1;--v;
			p=(p+k*last_ans)%(S+1);
			if(p>=ed.front().a){
				wt(last_ans=query(mnd[0],fd(0,v),0,n-1),'\n');
			}else{
				int l(0),r(m-1),mid;
				while(l<r){
					mid=(l+r+1)>>1;
					if(ed[mid].a>p){
						l=mid;
					}else{
						r=mid-1;
					}
				}
				wt(last_ans=query(mnd[l+1],fd(l+1,v),0,n-1),'\n');
			}
		}

		f.shrink_to_fit();
		s.shrink_to_fit();
		mnd.shrink_to_fit();
		t.shrink_to_fit();
	}
}int main(){if(___coding)freopen("in.txt","r",stdin);___main();___flush();return 0;}