交了1e18发，也剪了枝就是T7个点……

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int kmaxn=1e5+5;
const int kmaxm=2e5+5;
const int kmaxk=55;
struct edge{
	int nxt;
	int w;
	int to;
}e[kmaxm],E[kmaxm];
int k,m,n,p,t;
int cnt,cnt2,Head[kmaxn],head[kmaxn],dis[kmaxn],f[kmaxn][kmaxk];
int flag;
int vis[kmaxn];
int ans;
bool lis[kmaxn][kmaxk];
queue<int> q;
void add(int x,int y,int w){
	cnt++;
	e[cnt].to=y;
	e[cnt].w=w;
	e[cnt].nxt=Head[x];
	Head[x]=cnt;
}
void add1(int x,int y,int w){
	cnt2++;
	E[cnt2].to=y;
	E[cnt2].w=w;
	E[cnt2].nxt=head[x];
	head[x]=cnt2;
}
void spfa(int s){
	q.push(s);
	dis[s]=vis[s]=0;
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		vis[x]=0;
		for (int i=head[x];i;i=E[i].nxt){
			int t=E[i].to;
			if(dis[t]>dis[x]+E[i].w) {
				dis[t]=dis[x]+E[i].w;
				if(!vis[t]) {
					q.push(t);
					vis[t]=1;
				}
			}
		}
	}
} 
int dfs(int h,int b){	
	if(lis[h][b]==1){
		flag=1;
		return 0;
	}
	if(f[h][b]==1){
		return f[h][b];
	}
	int num=0;
	lis[h][b]=true;	
	for (int i=Head[h];i;i=e[i].nxt){
		int t=e[i].to;
		int lp=b-(dis[t]+e[i].w-dis[h]);
		if(lp>k||lp<0){
			continue;	
		} 
		num=(num+dfs(t,lp))%p;
	}
	lis[h][b]=false;
	if(h==n&&b==0){
		num++;
	}	
	return f[h][b]=num;
}
signed main(){
	cin>>t;
	while(t--){
		flag=0;
		ans=0;
		cnt=cnt2=1;
		memset(f,0,sizeof(f));
		memset(Head,0,sizeof(Head));
		memset(head,0,sizeof(head));
		memset(dis,0x3f,sizeof(dis));
		memset(vis,0,sizeof(vis));
		memset(lis,false,sizeof(lis));
		while(!q.empty()){
			q.pop();
		} 		
		cin>>n>>m>>k>>p;
		for (int i=1;i<=m;i++){
			int x,y,z;
			cin>>x>>y>>z;
			add(x,y,z);
			add1(y,x,z);
		}
		spfa(n);
		for (int i=0;i<=k;i++){			
			ans=(ans+dfs(1,i))%p;
		}
		if(flag){
			cout<<-1<<"\n";
		}else{
			cout<<ans%p<<"\n";
		}
	}
	return 0;
}