#include <bits/stdc++.h>

#define N 400005

#define ll long long

#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)

using namespace std;

int n,m,rt[N];

struct Edge {

	int u,v,l,a;

}e[N];

bool cmp(Edge a,Edge b) {

	return a.a>b.a;

}

namespace Dijkstra {

    struct Node {

    	int u;

    	ll dis;

    	Node(int u=0,ll dis=0):u(u),dis(dis){}

    	bool operator<(Node a)const {

    		return a.dis<dis;

    	}

    };

    priority_queue<Node>q;

	int edges,s;

	ll dis[N];

	int hd[N],nex[N<<1],val[N<<1],to[N<<1],done[N];

	void addedge(int u,int v,int c) {

		nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;

	}

	void re() {

		edges=0;

		memset(hd,0,sizeof(hd));

		memset(dis,0,sizeof(dis));

		memset(done,0,sizeof(done));

	}

	void solve() {

		memset(dis,0x3f,sizeof(dis));

		dis[s]=0;

		q.push(Node(s,0));

		while(!q.empty()) {

			Node e=q.top();q.pop();

			if(done[e.u]) continue;

			done[e.u]=1;

			for(int i=hd[e.u];i;i=nex[i])

				if(dis[to[i]]>dis[e.u]+val[i]) {

					dis[to[i]]=dis[e.u]+val[i];

					q.push(Node(to[i], dis[to[i]]));

				}

		}

	}

};

namespace ufs {

	#define ls t[now].lson

	#define rs t[now].rson

	struct Node {

		ll min;

		int fa,size,lson,rson;

	}t[N*50];

	int tot;

	void build(int &now,int l,int r) {

		now=++tot;

		if(l==r) {

			t[now].fa=l;

			t[now].size=1;

			t[now].min=Dijkstra::dis[l];

			return;

		}

		int mid=(l+r)>>1;

		if(l<=mid) build(ls,l,mid);

		if(r>mid)  build(rs,mid+1,r);

	}

	void update(int pre,int &now,int l,int r,int p,Node e) {

		now=++tot;

		t[now]=t[pre];

		if(l==r) {

			t[now].size=e.size;

			t[now].fa=e.fa;

			t[now].min=e.min;

			return;

		}

		int mid=(l+r)>>1;

		if(p<=mid) update(t[pre].lson,t[now].lson,l,mid,p,e);

		else update(t[pre].rson,t[now].rson,mid+1,r,p,e);

	}

	Node query(int now,int l,int r,int p) {

		if(l==r) return t[now];

		int mid=(l+r)>>1;

		if(p<=mid) return query(ls,l,mid,p);

		else return query(rs,mid+1,r,p);

	}

	Node find(int id,int x) {

	    Node p=query(rt[id],1,n,x);

	    return p.fa==x?p:find(id,p.fa);

	}

	void merge(int id,int x,int y) {

		Node a=find(id,x),b=find(id,y);

		if(a.fa!=b.fa) {

			if(a.size<b.size) swap(a,b);

			int rt1=0,rt2=0,A=a.fa,B=b.fa;

			a.size+=b.size;

			a.min=min(a.min,b.min);

			a.fa=b.fa=A;

			update(rt[id], rt1, 1, n, A, a);

			update(rt1, rt2, 1, n, B, b);

			rt[id+1]=rt2;

		}

		else rt[id+1]=rt[id];

	}

	void re() {

		for(int i=1;i<=tot;++i) t[i].lson=t[i].rson=t[i].size=t[i].min=t[i].fa=0;

		tot=0;

	}

	#undef ls

	#undef rs

};

void work() {

	int i;

	scanf("%d%d",&n,&m);

	for(i=1;i<=m;++i) {

		scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].l,&e[i].a);

		Dijkstra::addedge(e[i].u,e[i].v,e[i].l);

		Dijkstra::addedge(e[i].v,e[i].u,e[i].l);

	}

	Dijkstra::s=1;

	Dijkstra::solve();

	sort(e+1,e+1+m,cmp);

	ufs::build(rt[0],1,n);

	for(i=1;i<=m;++i) ufs::merge(i-1,e[i].u,e[i].v);

	ll lastans=0;

	int Q,K,S;

    scanf("%d%d%d",&Q,&K,&S);

    for(i=1;i<=Q;++i) {

    	int v,p;

    	scanf("%d%d",&v,&p);

    	v=(v+K*lastans-1)%n+1;

    	p=(p+K*lastans)%(S+1);

    	if(e[m].a>p) printf("0\n"),lastans=0;

    	else {

    		int l=0,r=m,mid=0,ans=0;

    		while(l<=r) {

    			mid=(l+r)>>1;

    			if(e[mid].a>p) {

    				ans=mid,l=mid+1;

    			}

    			else r=mid-1;

    		}

    		ufs::Node e=ufs::find(ans,v);

    		printf("%lld\n",lastans=e.min);

    	}

    }

    memset(rt,0,sizeof(rt));

    Dijkstra::re();

    ufs::re();

}

int main() {

	// setIO("input");

	int T,i;

	scanf("%d",&T);

	for(i=1;i<=T;++i) work();

	return 0;

}