长度1418！

#include<bits/stdc++.h>
#define rep(i,r) for(int i=1;i<=r;i++)
#define per(r,l) for(int i=r;i>=l;i--)
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;const int N=2e5+5;
int n,m,q,k,s,u,v,w,lst,cnt,head[N],dis[N*2],sz,ufs[N*2],fa[N*2][18],a[N*2],T;
struct edge{int v,nxt,w;}e[N*4];
void add(int u,int v,int w){e[++cnt]=(edge){v,head[u],w};head[u]=cnt;}
struct node{int u,d;bool operator<(const node&b)const{return d>b.d;}};
void dji(){priority_queue<node>q;mem(dis,63),dis[1]=0,q.push((node){1,0});while(!q.empty()){node t=q.top();q.pop();if(t.d>dis[t.u])continue;for(int i=head[t.u],v;v=e[i].v;i=e[i].nxt)if(t.d+e[i].w<dis[v])q.push((node){v,dis[v]=t.d+e[i].w});}}
struct Edge{int u,v,w;bool operator<(const Edge&b)const{return w>b.w;}}E[N*2];
int find(int x){return x==ufs[x]?x:ufs[x]=find(ufs[x]);}
void kru(){mem(head,cnt=0),mem(fa,0),sz=n;rep(i,n*2-1)ufs[i]=i;sort(E+1,E+m+1);rep(i,m)if((u=find(E[i].u))^(v=find(E[i].v))){a[fa[u][0]=ufs[u]=fa[v][0]=ufs[v]=++sz]=E[i].w;dis[sz]=min(dis[u],dis[v]);if(sz==n*2-1)break;}per(sz,1)rep(j,17)fa[i][j]=fa[fa[i][j-1]][j-1];}
int main(){cin>>T;while(T--){cin>>n>>m;mem(head,lst=cnt=0);rep(i,m){scanf("%d%d%d%d",&E[i].u,&E[i].v,&w,&E[i].w);add(E[i].u,E[i].v,w),add(E[i].v,E[i].u,w);}dji(),kru();cin>>q>>k>>s;while(q--){scanf("%d%d",&u,&w);u=(u+k*lst-1)%n+1;w=(w+k*lst)%(s+1);per(17,0)if(fa[u][i]&&a[fa[u][i]]>w)u=fa[u][i];printf("%d\n",lst=dis[u]);}}}