#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

typedef long long ll;

int const maxn=2e5+,maxm=4e5+,inf=0x3f3f3f3f;

int T,n,m,K,p,hd[maxn],ct,head[maxn],xt;

int f[maxn][],dis[maxn],s[maxn][];

bool v[maxn][],in[maxn],vis[maxn];

queue<int>q;

queue<int>ff;

struct N{

    int to,nxt,w;

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

}ed[maxm],edge[maxm];

void add(int x,int y,int z){ed[++ct]=N(y,hd[x],z); hd[x]=ct;}

void add2(int x,int y,int z){edge[++xt]=N(y,head[x],z); head[x]=xt;}

void spfa()

{

    while(q.size())q.pop();

    memset(vis,,sizeof vis);

    memset(dis,0x3f,sizeof dis);

    dis[]=; vis[]=; q.push();

    while(q.size())

    {

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

        for(int i=hd[x],u;i;i=ed[i].nxt)

            if(dis[u=ed[i].to]>dis[x]+ed[i].w)

            {

                dis[u]=dis[x]+ed[i].w;

                if(!vis[u])vis[u]=,q.push(u);

            }

    }

}

void bfs()

{

    while(q.size())q.pop();

    in[n]=; q.push(n);

    while(q.size())

    {

        int x=q.front(); q.pop();

        for(int i=head[x],u;i;i=edge[i].nxt)

        {

            if(in[u=edge[i].to])continue;

            in[u]=; q.push(u);

        }

    }

}

int dfs(int x,int w)

{

    if(w<)return ;

    else if(v[x][w])return -inf;

    else if(s[x][w]!=-)return s[x][w];

    else

    {

        int ret=; v[x][w]=;

        if(x==n)ret++;//

        for(int i=hd[x],u;i;i=ed[i].nxt)

        {

            if(!in[u=ed[i].to])continue;//!

            int tmp=dfs(u,w-(ed[i].w-(dis[u]-dis[x])));

            if(tmp==-inf)return -inf;

            else ret=(ret+tmp)%p;//(ret+=tmp)%=p RE?

        }

        v[x][w]=;

        s[x][w]=ret%p;

        return ret;

    }

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d%d",&n,&m,&K,&p);

        ct=; xt=;

        memset(hd,,sizeof hd);

        memset(head,,sizeof head);

        for(int i=,x,y,z;i<=m;i++)

        {

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

            add(x,y,z); add2(y,x,z);

        }

        memset(in,,sizeof in);

        spfa(); bfs();

        memset(v,,sizeof v);

        memset(s,-,sizeof s);

        int ans=dfs(,K);

        if(ans==-inf)printf("-1\n");

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

    }

    return ;

}