#include<bits/stdc++.h>

 using namespace std;

 const int N=;

 struct node

 {

     int to,nex,w;

 }e[N],z[N];

 int cnt,cnt1,head[],head2[];

 int add(int x,int y,int w)

 {

     e[++cnt1].to=y;e[cnt1].w=w;e[cnt1].nex=head[x];head[x]=cnt1;

     z[++cnt].to=x;z[cnt].w=w;z[cnt].nex=head2[y];head2[y]=cnt;

 }

 int f[][];

 int d1[],d2[],d[],qq[N<<];

 bool v[];int n,m,k,p;

 void update(int &a,int b)

 {

     a=(a+b)%p;

 }

 queue<int>q;

 void work()

 {

     scanf("%d%d%d%d",&n,&m,&k,&p);cnt=,cnt1=;

     memset(head,,sizeof(head));

     memset(head2,,sizeof(head2));

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

     {

         int x,y,w;

         scanf("%d%d%d",&x,&y,&w);

         add(x,y,w);

     }

     memset(v,,sizeof(v));memset(d1,0x3f,sizeof(d1));

     q.push();d1[]=;v[]=;

     while(!q.empty())

     {

         int x=q.front();q.pop();v[x]=;

         for(int i=head[x];i;i=e[i].nex)

         {

             int y=e[i].to;

             if(d1[y]>d1[x]+e[i].w)

             {

                 d1[y]=d1[x]+e[i].w;

                 if(!v[y])

                 {

                     q.push(y);v[y]=;

                 }

             }

         }

     }

     memset(v,,sizeof(v));memset(d2,0x3f,sizeof(d2));

     q.push(n);d2[n]=;v[n]=;

     while(!q.empty())

     {

         int x=q.front();q.pop();v[x]=;

         for(int i=head2[x];i;i=z[i].nex)

         {

             int y=z[i].to;

             if(d2[y]>d2[x]+z[i].w)

             {

                 d2[y]=d2[x]+z[i].w;

                 if(!v[y])

                 {

                     q.push(y);v[y]=;

                 }

             }

         }

     }

    

     int top=;memset(d,,sizeof(d));

     for(int i=;i<=n;++i)

     for(int j=head[i];j;j=e[j].nex)

     {

         if(d1[i]+e[j].w==d1[e[j].to])d[e[j].to]++;

     }

     for(int i=;i<=n;++i)if(!d[i])qq[++top]=i;

     for(int i=;i<=top;++i)

     {

         int x=qq[i];

         for(int j=head[x];j;j=e[j].nex)

         if(d1[x]+e[j].w==d1[e[j].to])

         {

             int y=e[j].to;

             d[y]--;

             if(d[y]==)qq[++top]=y;

         }

     }

     for(int i=;i<=n;++i)

     if(d[i]&&d1[i]+d2[i]<=d1[n]+k)

     {

         puts("-1");return;

     }

     int ans=;

     memset(f,,sizeof(f));

     f[][]=;

     for(int i=;i<=k;++i)

     {

         for(int j=;j<=top;++j)

         for(int u=head[qq[j]];u;u=e[u].nex)

         {

             if(d1[qq[j]]+e[u].w==d1[e[u].to])

             update(f[e[u].to][i],f[qq[j]][i]);

         }

        

         for(int j=;j<=n;++j)

         for(int u=head[j];u;u=e[u].nex)

         {

             if(d1[j]+e[u].w!=d1[e[u].to]&&i+d1[j]-d1[e[u].to]+e[u].w<=k)

             update(f[e[u].to][i+d1[j]-d1[e[u].to]+e[u].w],f[j][i]);

         }

     }

     for(int i=;i<=k;++i)

     update(ans,f[n][i]);

     printf("%d\n",ans);

     return ;

 }

 int main()

 {

     int t;scanf("%d",&t);

     while(t--)

     {

         work();

     }

     return ;

 }