代码如下：

#include<bits/stdc++.h>
using namespace std;
int t,n,m,k,p,num[100010],x,y,z,dis[100010],u,sum;
struct node{
	int q,s;
};
bool vis[100010]; 
vector<node> a[100010];
queue<int> qt;
void dfs(int now,int s,string str){
	if(s>u) return;
	if(now==n){
		sum=(sum+1)%p;
		return;
	}
	for(int i=0;i<num[now];i++){
		if(!vis[a[now][i].q]){
			vis[a[now][i].q]=1;
			dfs(a[now][i].q,s+a[now][i].s,str+char(a[now][i].q+'0'));
			vis[a[now][i].q]=0;
		}
	}
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d",&n,&m,&k,&p);
		for(int i=1;i<=n;i++) a[i].clear();
		while(m--){
			scanf("%d%d%d",&x,&y,&z);
			a[x].push_back({y,z});
			num[x]++;
		}
		memset(vis,0,sizeof(vis));
		memset(dis,127,sizeof(dis));
		dis[1]=0;
		vis[1]=1;
		qt.push(1);
		while(!qt.empty()){
			int now=qt.front();
			vis[now]=0;
			for(int j=0;j<num[now];j++){
				if(dis[a[now][j].q]>dis[now]+a[now][j].s){
					dis[a[now][j].q]=dis[now]+a[now][j].s;
					if(!vis[a[now][j].q]){
						qt.push(a[now][j].q);
						vis[a[now][j].q]=1;
					}
				}
			}
			qt.pop();
		}
		u=dis[n]+k;
		memset(vis,0,sizeof(vis));
		vis[1]=1;
		sum=0;
		dfs(1,0,"1");
		printf("%d\n",sum);
	}
	return 0;
}