```cpp
#include<cstdio>
typedef unsigned ui;
const ui M=1e5+5;
ui T,n,m,k,G,P,cnt,h[M],d[M],D[M],t[M<<2];ui u[M<<1],v[M<<1],val[M<<1];
struct Edge{
ui v,nx,val;
}e[M<<2];
inline ui id(const ui&u,const ui&k){
return k*n+u;
}
inline ui Add(const ui&a,const ui&b){
return a+b>=P?a+b-P:a+b;
}
inline void Add(const ui&u,const ui&v,const ui&val){
e[++cnt]=(Edge){v,h[u],val};h[u]=cnt;
}
inline void Mdf(ui u,const ui&V){
if(~V)d[u]=V;for(D[u]=V,u=u+G>>1;u;u>>=1)t[u]=t[u<<1|(D[t[u<<1]]>D[t[u<<1|1]])];
}
inline void Dijkstra(){
ui u,v,E;for(u=2;u<=n;++u)D[u]=0x7fffffff;D[1]=0;for(G=1;G<=n+1;G<<=1);
for(u=1;u<=n;++u)t[u+G]=u;for(u=G-1;u>=1;--u)t[u]=t[u<<1|(D[t[u<<1]]>D[t[u<<1|1]])];
while(u=t[1])for(Mdf(u,-1),E=h[u];E;E=e[E].nx)if(d[u]+e[E].val-D[v=e[E].v]>>31)Mdf(v,d[u]+e[E].val);
for(u=1;u<=G+n;++u)t[u]=0;
}
struct Graph{
ui cnt,f[M*51],h[M*51],hd[M*51];bool t[M*51],vis[M*51],tag[M*51];
struct Edge{
ui v,nx;
}e[M*102],E[M*102];
inline void Add(const ui&u,const ui&v){
++cnt;e[cnt]=(Edge){v,h[u]};E[cnt]=(Edge){u,hd[v]};hd[v]=h[u]=cnt;
}
void init(const ui&u){
if(t[u])return;t[u]=true;for(ui e=hd[u];e;e=E[e].nx)init(E[e].v);
}
ui DFS(const ui&u){
ui E,x;bool typ(false);if(vis[u])return-1;if(tag[u])return f[u];tag[u]=true;vis[u]=true;
for(E=h[u];E;E=e[E].nx,f[u]=::Add(f[u],x))if(!~(x=DFS(e[E].v)))typ=true;
return vis[u]=false,typ&&t[u]?-1:f[u];
}
}g;
signed main(){
ui i,j;scanf("%u",&T);D[0]=-1;
while(T--){
scanf("%u%u%u%u",&n,&m,&k,&P);for(i=1;i<=k;++i)g.Add(id(n,i-1),id(n,i));g.f[id(n,k)]=1;
for(i=1;i<=m;++i)scanf("%u%u%u",u+i,v+i,val+i),Add(u[i],v[i],val[i]);Dijkstra();
for(i=1;i<=m;++i)if(d[u[i]]<=d[v[i]]){
for(j=0;j+d[u[i]]+val[i]-d[v[i]]<=k;++j)g.Add(id(u[i],j),id(v[i],j+d[u[i]]+val[i]-d[v[i]]));
}
g.init(id(n,k));for(i=1;i<=id(n,k);++i)if(!g.t[i])g.tag[i]=true;
j=g.DFS(1);printf(!~j?"-1\n":"%u\n",j);cnt=g.cnt=0;
for(i=1;i<=n;++i)for(h[i]=D[i]=j=0;j<=k+1;++j){
g.f[id(i,j)]=g.h[id(i,j)]=g.vis[id(i,j)]=g.tag[id(i,j)]=g.t[id(i,j)]=g.hd[id(i,j)]=0;
}
}
}
```
可能有亿点点压行，但是这个Dij是过了洛谷模板题的
by Prean @ 2021-12-03 20:26:10