#include<bits/stdc++.h>
using namespace std;
#define N 1600005
int T,n,m;
struct edge
{
  int u,v,l,a;
}eg[N];
struct edg
{
  int v,dis;
}e[N];
int cnt;
vector<int> mp[N];
vector<int> tr[N];
int dis[N];
bool vis[N];
bool cmp(edge x,edge y)
{
  return x.a>y.a;
}
priority_queue<pair<int,int> > qu;
void dij()
{
  memset(vis,0,sizeof(vis));
  memset(dis,0x3f,sizeof(dis));
  dis[1]=0;
  qu.push(make_pair(0,1));
  while(qu.size())
  {
    int u=qu.top().second;
    qu.pop();
    if(vis[u])
      continue;
    vis[u]=1;
    for(int i=0;i<mp[u].size();i++)
    {
      int v=e[mp[u][i]].v,w=e[mp[u][i]].dis;
      if(dis[v]>dis[u]+w)
      {
        dis[v]=dis[u]+w;
        qu.push(make_pair(-dis[v],v));
      }
    }
  }
}
struct bcj
{
  int fa[N];
  int getfa(int x)
  {
    if(fa[x]==x)
      return x;
    else
      return fa[x]=getfa(fa[x]);
  }
}bc;
int kst[N];
int fa[N][20],zson[N];
void dfs(int x)
{
  for(int i=1;i<=19;i++)
    fa[x][i]=fa[fa[x][i-1]][i-1];
  for(int i=0;i<tr[x].size();i++)
  {
    fa[tr[x][i]][0]=x;
    dfs(tr[x][i]);
    zson[x]=min(zson[x],zson[tr[x][i]]);
  }
  if(tr[x].size()==0)
    zson[x]=dis[x];
}
int q,k,s;
int main()
{
  scanf("%d",&T);
  while(T--)
  {
    memset(zson,0x3f,sizeof(zson));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n<<1;i++)
      bc.fa[i]=i,mp[i].clear();
    for(int i=1;i<=m;i++)
    {
      int x,y,a,b;
      scanf("%d%d%d%d",&x,&y,&a,&b);
      eg[i]=(edge){x,y,a,b};
      mp[x].push_back(++cnt);
      e[cnt]=(edg){y,a};
      mp[y].push_back(++cnt);
      e[cnt]=(edg){x,a};
    }
    dij();
    sort(eg+1,eg+1+m,cmp);
    int cntcc=0;
    for(int i=1;i<=m&&cntcc<=n-1;i++)
    {
      int kk=bc.getfa(eg[i].u);
      int kt=bc.getfa(eg[i].v);
      if(kk!=kt)
      {
        cntcc++;
        kst[cntcc+n]=eg[i].a;
        tr[cntcc+n].push_back(kk);
        tr[cntcc+n].push_back(kt);
        bc.fa[kk]=bc.fa[kt]=n+cntcc; 
      }
    }
    dfs(n+cntcc);
    scanf("%d%d%d",&q,&k,&s);
    int lastans=0;
    for(int 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);
      for(int i=19;i>=0;i--) 
        if(kst[fa[v][i]]>p)
          v=fa[v][i];
      printf("%d\n",zson[v]);
      lastans=zson[v];
    }   
  }
  return 0;
}