#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=200005;
int n,m,Q,K,S,dis[MAXN];
struct node{int to,dis,h;};
vector <node> a[MAXN];
bool only_tag,chain_tag;
void read(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) a[i].clear();
memset(dis,63,sizeof(dis));
int u,v,w,h;
only_tag=chain_tag=true;
for (int i=1;i<=m;i++){
scanf("%d%d%d%d",&u,&v,&w,&h);
if (h!=1) only_tag=false;
if (u+1!=v) chain_tag=false;
a[u].push_back((node){v,w,h});
a[v].push_back((node){u,w,h});
}
scanf("%d%d%d",&Q,&K,&S);
}
queue <int> q;
void spfa(){
q.push(1);
dis[1]=0;
while (!q.empty()){
int o=q.front(); q.pop();
for (int i=0;i<a[o].size();i++){
int v=a[o][i].to,d=a[o][i].dis;
if (dis[v]>dis[o]+d) dis[v]=dis[o]+d,q.push(v);
}
}
}
void solve(){
int p,v;
if (only_tag){
for (int i=1;i<=Q;i++){
scanf("%d%d",&p,&v);
if (v>=1) printf("%d\n",dis[p]);
else puts("0");
}
}
else if (chain_tag){
for (int i=1;i<=Q;i++){
scanf("%d%d",&p,&v);
int ans=0;
while (p!=1){
int choice=a[p][0].to!=p-1;
if (a[p][choice].h<=v) {ans+=dis[p];break;}
p--;
}
printf("%d\n",ans);
}
}
}
int T;
int main(){
scanf("%d",&T);
while (T--){
read();
spfa();
solve();
}
return 0;
}