#include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 #define rg register

 #define N 200010

 using namespace std;

 int T,n,m,k,p,tot,last[N],dis[N],pos[N],f[N][];

 bool in[N][];

 struct edge{int to,pre,dis;}e[N];

 struct heap{int p,d;}h[N];

 struct rec{int u,v,w;}r[N];

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=='-'&&(f=-),c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 inline void MOD(int &k){if(k>=p) k-=p;}

 inline void up(int x){

     int fa;

     while((fa=x>>)&&h[fa].d>h[x].d) swap(h[x],h[fa]),swap(pos[h[x].p],pos[h[fa].p]),x=fa;

 }

 inline void down(int x){

     int son;

     while((son=x<<)<=tot){

         if(h[son+].d<h[son].d&&son<tot) son++;

         if(h[son].d<h[x].d) swap(h[x],h[son]),swap(pos[h[x].p],pos[h[son].p]),x=son;

         else return;

     }

 }

 inline void dijkstra(int x){

     for(rg int i=;i<=n;i++) dis[i]=1e9;

     h[pos[x]=tot=]=(heap){x,dis[x]=};

     while(tot){

         int now=h[].p; pos[h[tot].p]=; h[]=h[tot--]; if(tot) down();

         for(rg int i=last[now],to;i;i=e[i].pre)if(dis[to=e[i].to]>dis[now]+e[i].dis){

             dis[to]=dis[now]+e[i].dis;

             if(!pos[to]) h[pos[to]=++tot]=(heap){to,dis[to]};

             else h[pos[to]].d=dis[to];

             up(pos[to]);

         }

     }

 }

 int dfs(int x,int d){

     if(in[x][d]) return -;

     if(f[x][d]) return f[x][d];

     in[x][d]=; f[x][d]=(x==n)?:;

     for(rg int i=last[x],to,num;i;i=e[i].pre){

         int tmp=-dis[x]+dis[to=e[i].to]+e[i].dis;

         if(tmp<=d){

             if((num=dfs(to,d-tmp))==-) return -;

             MOD(f[x][d]+=num);

         }

     }

     return in[x][d]=,f[x][d];

 }

 inline void Pre(){

     memset(in,,sizeof(in));

     memset(last,,sizeof(last));

     memset(pos,,sizeof(pos));

     memset(f,,sizeof(f));

     tot=;

 }

 int main(){

     T=read();

     while(T--){

         Pre();

         n=read(); m=read(); k=read(); p=read();

         for(rg int i=,u,v;i<=m;i++){

             r[i].u=u=read(); r[i].v=v=read();

             e[++tot]=(edge){u,last[v],r[i].w=read()}; last[v]=tot;

         }

         dijkstra(n);

         memset(last,,sizeof(last)); tot=;

         for(rg int i=;i<=m;i++){

             int u=r[i].u,v=r[i].v;

             e[++tot]=(edge){v,last[u],r[i].w}; last[u]=tot;

         }

         printf("%d\n",dfs(,k));

     }

     return ;

 }