#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define ll long long

using namespace std;

const int N=1e5+,M=2e5+,S=,INF=0x3f3f3f3f;

int T,n,m,K,mod,hd[N],thd[N],xnt,tnt,dis[N],dit[N],f[N][S],ans;

bool vis[N],flag,gx[N][S];

struct Ed{

    int nxt,to,w;

    Ed(int n=,int t=,int w=):nxt(n),to(t),w(w) {}

}ed[M],ted[M];

int rdn()

{

    int ret=;char ch=getchar();

    while(ch>''||ch<'')ch=getchar();

    while(ch>=''&&ch<='')(ret*=)+=ch-'',ch=getchar();

    return ret;

}

priority_queue<pair<int,int> >q;

void dj()

{

    memset(dis,0x3f,sizeof dis);dis[]=;

    memset(vis,,sizeof vis);

    q.push(make_pair(-dis[],));

    while(q.size())

    {

        int k=q.top().second;q.pop();

        while(q.size()&&vis[k])k=q.top().second,q.pop();

        if(vis[k])break;vis[k]=;

        for(int i=hd[k],v;i;i=ed[i].nxt)

            if(dis[v=ed[i].to]>dis[k]+ed[i].w)

                dis[v]=dis[k]+ed[i].w,q.push(make_pair(-dis[v],v));

    }

    memset(dit,0x3f,sizeof dit);dit[n]=;

    memset(vis,,sizeof vis);

    q.push(make_pair(-dit[n],n));

    while(q.size())

    {

        int k=q.top().second;q.pop();

        while(q.size()&&vis[k])k=q.top().second,q.pop();

        if(vis[k])break;vis[k]=;

        for(int i=thd[k],v;i;i=ted[i].nxt)

            if(dit[v=ted[i].to]>dit[k]+ted[i].w)

                dit[v]=dit[k]+ted[i].w,q.push(make_pair(-dit[v],v));

    }

}

int dfs(int cr,int k)

{

    if(gx[cr][k]){flag=;return -;}

    if(f[cr][k])return f[cr][k];

    if(cr==n)f[cr][k]=;//别return f[cr]=1,万一在终点连了一个0环

    gx[cr][k]=;

    for(int i=hd[cr],v;i;i=ed[i].nxt)

    {

        int w=dis[cr]+k+ed[i].w-dis[v=ed[i].to];

        if(w>K||(ll)dis[v]+w+dit[v]>dis[n]+K)continue;

        (f[cr][k]+=dfs(v,w))%=mod;

        if(flag)return -;

    }

    gx[cr][k]=;//!

    return f[cr][k];

}

int main()

{

    T=rdn();

    while(T--)

    {

        memset(hd,,sizeof hd);xnt=;

        memset(thd,,sizeof thd);tnt=;

        n=rdn();m=rdn();K=rdn();mod=rdn();

        int x,y,z;

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

        {

            x=rdn();y=rdn();z=rdn();

            ed[++xnt]=Ed(hd[x],y,z);hd[x]=xnt;

            ted[++tnt]=Ed(thd[y],x,z);thd[y]=tnt;

        }

        dj();

        memset(f,,sizeof f);memset(gx,,sizeof gx);

        flag=;ans=dfs(,);

        if(flag)ans=-;

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

    }

    return ;

}