#include<bits/stdc++.h>
#define reg register
using namespace std;
const int N=2e5+10;
struct edge{int from,to,weight;}E[N];
int n,m,k,p,head[N],nxt[N],cntedge;
inline int add_edge(int from,int to,int weight)
{//添加边,链式前向星存储图
	E[++cntedge]=(edge){from,to,weight};
	nxt[cntedge]=head[from];
	head[from]=cntedge;
	return 0;
}
int read()
{
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
typedef pair<int,int> pairii;
priority_queue<pairii,vector<pairii>,greater<pairii> > Q;
int disS[N],disT[N];
bool vis[N];
int dijkstra(int *dis,int s)
{//优先队列优化的DJ算法
	for(int i=1;i<=n;i++) dis[i]=2e9,vis[i]=0;
	Q.push(pairii(dis[s]=0,s));
	while (!Q.empty())
	{
		int v=Q.top().second;Q.pop();
		if(vis[v]) continue;
		vis[v]=1;
		for(int i=head[v];i;i=nxt[i])
		if(dis[E[i].to]>dis[v]+E[i].weight)
		{//松弛操作
			int u=E[i].to;
			Q.push(pairii(dis[u]=dis[v]+E[i].weight,u));
		}
	}
	return 0;
}
int u[N],v[N],w[N],dfn[N],low[N],scc[N],sta[N],top,dfs_clock;
bool ins[N];
int tarjan(int x)
{//tarjan判环
	dfn[x]=low[x]=++dfs_clock;//时间戳
	ins[sta[++top]=x]=1;//进栈状态置1
	for(int i=head[x];i;i=nxt[i])
	{
		int v=E[i].to;
		if(!dfn[v])
			tarjan(v),low[x]=min(low[x],low[v]);
		else
			if(ins[v])
				low[x]=min(low[x],dfn[v]);
	}
	if(dfn[x]==low[x])
	{/*如果有强联通分量即环，那么将环上所有顶点的scc后继属性设置为环上DFN最小的结点的编号*/
		while(sta[top]!=x)
			scc[sta[top]]=x,ins[sta[top--]]=0;
		scc[x]=x;ins[x]=0;top--;
	}
	return 0;
}
inline int inc(int &x,int y)
{
	x+=y;
	if(x>=p)x%=p;
	return 0;
}
int degree[N][60],dp[N][60],q[N*60][2];
void outpt()
{
	for(reg int i=1;i<=n;i++)
		{
			for(reg int j=0;j<=k;j++)
				cout<<dp[i][j]<<' ';
			cout<<endl;
		}
		cout<<endl<<endl;
}
int work()
{
	scanf("%d%d%d%d",&n,&m,&k,&p);
	for(int i=1;i<=m;i++) u[i]=read(),v[i]=read(),w[i]=read();
	cntedge=0;
	for(int i=1;i<=n;i++) head[i]=0;
	for(int i=1;i<=m;i++) add_edge(v[i],u[i],w[i]);//反向边v-u
	/*将所有边反向，求N到其它结点的最短路*/
	dijkstra(disT,n);//起点为n到其它顶点
	//for(int i=1;i<=n;i++)cout<<disT[i]<<' ';cout<<endl;
	cntedge=0;
	for(int i=1;i<=n;i++) head[i]=0;
	for(int i=1;i<=m;i++) add_edge(u[i],v[i],w[i]);//正向边
	/*求1点到其它顶点的最短路*/
	dijkstra(disS,1);//起点为1到其它顶点
	
	cntedge=0;
	for(int i=1;i<=n;i++) head[i]=0;
	for(int i=1;i<=m;i++)
		if(!w[i])//构造所有0权边组成的图，寻找是否有0环
			add_edge(u[i],v[i],w[i]);
	dfs_clock=0;
	for(int i=1;i<=n;i++)dfn[i]=low[i]=scc[i]=0;//tarjan初始化，寻找0权环
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);/*在0权图上以尚未被访问的每个点为起点运行tarjan，寻找0环，
	如果存在scc属性设置为环上根结点的编号*/
	
	for(int i=1;i<=cntedge;i++)
	{//枚举0权图中的0权边
		int u=E[i].from,v=E[i].to;
		if(scc[u]==scc[v]&&disS[u]+disT[v]<=disS[n]+k)
		{/*如果存在0权环并且边u-v处在满足条件的路径上，即围绕0环会出现无穷多条满足条件的路径*/
			puts("-1");return 0;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=k;j++)//根据k将图分成k+1层,0~k
			dp[i][j]=degree[i][j]=0;
	//degree[i][j]表示第j层(0<=j<=k)，1~i的路径中不超过disS[i]+j时i点的入度
	cntedge=0;
	for(int i=1;i<=n;i++) head[i]=0;
	for(int i=1;i<=m;i++) add_edge(u[i],v[i],w[i]);
	for(int i=1;i<=m;i++)
	{//枚举每一条边，计算每一层i的入度
		int x=u[i],y=v[i];
		for(int j=0;j<=k;j++)
		{//位置pos=起点1到x最短路值+w(x-y)+j-起点1到y的最短路值
			int pos=disS[x]+w[i]+j-disS[y];
			if(pos<=k)
				degree[y][pos]++;//入度加1
		}
	}
	
	int size=0;
	for(reg int j=0;j<=k;j++)for(reg int i=1;i<=n;i++)
		
			if(!degree[i][j])//入度为0的点入队
				++size,q[size][0]=i,q[size][1]=j;
	/*
	dp[v][x]表示1~v的路径中,比disS[v]多x的条数。
	dp[v][dis[u]+j+w(u,v)-dis[v]]=SUM(dp[u][j])  0<=j<=k   dis[u]+j+w-dis[v]<=k
	*/
	dp[1][0]=1%p;
	for(reg int i=1;i<=size;i++)
	{//按照拓扑排序的顺序转移状态
		reg int u=q[i][0],j=q[i][1];
		reg int cnt=dp[u][j];
		for(reg int i=head[u];i;i=nxt[i])
		{
			reg int v=E[i].to,pv=disS[u]+j+E[i].weight-disS[v];
			if(pv<=k)
			{
				inc(dp[v][pv],cnt);
				
				if(!--degree[v][pv])//入度减1后为0,入队等待拓扑
					++size,q[size][0]=v,q[size][1]=pv;
			}
		}
	}
	
	int ans=0;
	for(int i=0;i<=k;i++)
		inc(ans,dp[n][i]);//累加dp[n][i]
	printf("%d\n",ans);
	return 0;
}
int main()
{
	freopen("2017park.in","r",stdin);
	freopen("2017park.out","w",stdout);
	int T;
	scanf("%d",&T);
	while (T--)work();
	return 0;
}