#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    struct edge
    {
        ll to,d,next;
        edge()
        {
            to=d=next=0;
        };
        edge(ll tov,ll dv,ll nextv)
        {
            to=tov,d=dv,next=nextv;
        };
    };
    
    ll T;
    ll n,m,t,p,esize,flag;
    ll a[200000+1];
    ll b[200000+1];
    ll c[200000+1];
    ll dis[100000+1];
    ll vis[100000+1];
    ll head1[100000+1];
    ll head2[100000+1];
    ll f[100000+1][50+1+1];
    ll v[100000+1][50+1+1];
    deque<ll> q;
    edge e1[200000+1];
    edge e2[200000+1];
    
    void add(ll x,ll y,ll d)
    {
        esize++;
        e1[esize]=edge(y,d,head1[x]);
        e2[esize]=edge(x,d,head2[y]);
        head1[x]=head2[y]=esize;
    }
    
    void spfa()
    {
        q.clear();
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[1]=0;
        for (vis[1]=1,q.push_back(1);!q.empty();)
        {
            ll now=q.front();
            vis[now]=0,q.pop_front();
            for (ll i=head1[now];i;i=e1[i].next)
            {
                ll to=e1[i].to,d=e1[i].d;
                if (dis[now]+d<dis[to])
                {
                    dis[to]=dis[now]+d;
                    if (!vis[to])
                        vis[to]=1,q.push_back(to);
                }
            }
        }
    }
    
    ll dfs(ll now,ll t)
    {
        if (f[now][t]!=-1)
            return f[now][t];
        v[now][t]=1;
        f[now][t]=0;
        for (ll i=head2[now];i;i=e2[i].next)
        {
            ll to=e2[i].to,d=e2[i].d;
            ll s=dis[now]+t-d-dis[to];
            if (s>=0)
            {
                if (v[to][s])
                    flag=1;
                f[now][t]=(f[now][t]+dfs(to,s))%p;
            }
        }
        v[now][t]=0;
        return f[now][t];
    }
    
    ll work()
    {
        spfa();
        memset(f,-1,sizeof(f));
        f[1][0]=1;
        memset(v,0,sizeof(v));
        ll ans=0;
        for (ll i=0;i<=t&&(!flag);i++)
            ans=(ans+dfs(n,i))%p;
        if (!flag)
            dfs(n,t+1);
        if (flag)
            return -1;
        else
            return ans;
    }
    
    void main()
    {
        while (~scanf("%lld",&T))
            for (ll rp=1;rp<=T;rp++)
            {
                flag=0;
                scanf("%lld%lld%lld%lld",&n,&m,&t,&p);
                esize=0;
                memset(head1,0,sizeof(head1));
                memset(head2,0,sizeof(head2));
                for (ll i=1;i<=m;i++)
                {
                    scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
                    add(a[i],b[i],c[i]);
                }
                printf("%lld\n",work());
            }
    }
}

int main()
{
    dts::main();
}