70pts

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e5+5;
int T,n,m,k,p;
vector<int>a[N<<1],b[N<<1];
int ans,dis[N],book[N],cnt[N],dp[N][55],nn;
queue<int>q;
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void spfa()
{
	dis[1]=0;
	book[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		book[u]=0;
		for(int i=0;i<a[u].size();i++)
		{
			int v=a[u][i],w=b[u][i];
			if(dis[v]>=dis[u]+w)
			{
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n)
				{
					ans=-1;
					return;
				}
				else
					book[v]=1,q.push(v);
			}
		}
	}
	for(int i=1;i<=n;i++)
		dis[i+n]=dis[i];
}
int dfs(int u,int k)
{
	if(k<0)
		return 0;
	if(dp[u][k])
		return dp[u][k];
	int res=0;
	for(int i=0;i<a[u].size();i++)
	{
		int v=a[u][i],w=b[u][i];
		res=(res+dfs(v,dis[u]-dis[v]+k-w))%p;
	}
	return dp[u][k]=res;
}
int main()
{
	T=read();
	while(T--)
	{
		n=read(),m=read(),k=read(),p=read();
		nn=n<<1;
		ans=0;
		memset(dp,0,sizeof dp);
		memset(dis,0x3f,sizeof dis);
		memset(book,0,sizeof book);
		for(int i=1;i<=nn;i++)
			a[i].clear(),b[i].clear();
		while(!q.empty())
			q.pop();
		for(int i=1;i<=m;i++)
		{
			int u=read(),v=read(),w=read();
			a[u].pb(v),b[u].pb(w);
			a[v+n].pb(u+n),b[v+n].pb(w);
		}
		spfa();
		if(ans==-1)
		{
			puts("-1");
			continue;
		}
//		dfs(n+1,0);
		dp[n+1][0]=1;
		for(int i=0;i<=k;i++)
			ans=(ans+dfs(n<<1,i))%p;
		printf("%d\n",ans);
	}
	return 0;
}