#include <algorithm>
#include <array>
// #include <bitset>
#include <cassert>
// #include <cctype>
// #include <climits>
// #include <cmath>
// #include <cstdarg>
#include <cstdint>
// #include <cstdio>
#include <cstdlib>
// #include <cstring>
// #include <ctime>
// #include <deque>
#include <fstream>
// #include <functional>
// #include <iomanip>
#include <iostream>
// #include <map>
// #include <memory>
#include <numeric>
#include <queue>
// #include <random>
// #include <ranges>
// #include <set>
// #include <sstream>
// #include <stack>
// #include <string>
// #include <tuple>
// #include <unordered_map>
// #include <unordered_set>
// #include <utility>
#include <vector>
#ifndef ONLINE_JUDGE
#define ___file_name "1"
#define ___debug_with_file
#else
// #define ___file_name ""
#endif
typedef int8_t i8;
typedef uint8_t u8;
typedef int16_t i16;
typedef uint16_t u16;
typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;

int T,n,m,q,k,S,tot,log2_n;
std::vector<i8> vs;
std::vector<int> ds,f,height;
std::vector<std::vector<int>> fa;
std::vector<std::vector<std::array<int,2>>> g;
struct node{
	int u,v,l,a;
	bool operator<(const node& other)const{
		return this->a>other.a;
	}
};
std::vector<node> e;
std::priority_queue<std::pair<int,int>> p;

void dijkstra(){
	vs.resize(n);
	std::fill(vs.begin(),vs.end(),0);
	ds.resize(n<<1);
	std::fill(ds.begin(),ds.end(),int(2e9));
	ds[0]=0;
	p.push(std::make_pair(0,0));
	for(int u,v,w;p.size();){
		u=p.top().second;p.pop();
		if(!vs[u]){
			vs[u]=1;
			for(auto& i:g[u]){
				v=i[0];w=i[1];
				if(ds[u]+w<ds[v]){
					ds[v]=ds[u]+w;
					p.push(std::make_pair(-ds[v],v));
				}
			}
		}
	}
}
int log_2(int k){
	int res(0);
	for(;k;k>>=1,++res);
	return res;
}
void dfs(int u,int father){
	fa[u][0]=father;
	for(int i(fa[u].size()-1);i;--i){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(auto& i:g[u]){
		if(i[0]!=father){
			dfs(i[0],u);
		}
	}
}
int fd(int k){
	return f[k]==k?k:f[k]=fd(f[k]);
}
void ___main(){
	for(std::cin>>T;T--;){
		std::cin>>n>>m;
		g.resize(n<<1);
		for(auto& i:g){
			i.clear();
		}
		e.resize(m);
		for(auto& i:e){
			std::cin>>i.u>>i.v>>i.l>>i.a;
			--i.u;--i.v;
			g[i.u].push_back(std::array<int,2>({i.v,i.l}));
			g[i.v].push_back(std::array<int,2>({i.u,i.l}));
		}
		dijkstra();
		for(auto& i:g){
			i.clear();
		}
		tot=n;
		std::sort(e.begin(),e.end());
		f.resize(n<<1);
		std::iota(f.begin(),f.end(),0);
		height.resize(n<<1);
		int u,v;
		for(auto& i:e){
			u=fd(i.u);v=fd(i.v);
			if(u!=v){
				f[u]=f[v]=tot;
				ds[tot]=std::min(ds[u],ds[v]);
				height[tot]=i.a;
				g[tot].push_back(std::array<int,2>({u,0}));
				g[tot].push_back(std::array<int,2>({v,0}));
				++tot;
			}
		}
		fa.resize(n<<1);
		log2_n=log_2(n);
		for(auto& i:fa){
			i.resize(log2_n+1);
			std::fill(i.begin(),i.end(),tot-1);
		}
		dfs(tot-1,tot-1);
		std::cin>>q>>k>>S;
		++S;
		int last_ans(0);
		for(int i(0),v,p;i<q;++i){
			std::cin>>v>>p;
			v=(v+k*last_ans-1)%n;
			p=(p+k*last_ans)%S;
			for(int j(log2_n);~j;--j){
				if(height[fa[v][j]]>p){
					v=fa[v][j];
				}
			}
			std::cout<<(last_ans=ds[v])<<'\n';
		}
	}
}
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);
#ifdef ___file_name
	std::ifstream input_file(___file_name".in");std::ofstream output_file(___file_name".out");
	std::streambuf *cinbuf(std::cin.rdbuf(input_file.rdbuf())),*coutbuf(std::cout.rdbuf(output_file.rdbuf()));
# ifdef ___debug_with_file
	std::ofstream debug_file(___file_name".debug");std::streambuf *cerrbuf(std::cerr.rdbuf(debug_file.rdbuf()));
# endif
#endif
	___main();
#ifdef ___file_name
	output_file.flush();std::cin.rdbuf(cinbuf);std::cout.rdbuf(coutbuf);
# ifdef ___debug_with_file
	debug_file.flush();std::cerr.rdbuf(cerrbuf);
# endif
#endif
	return 0;
}