Input: 2 5 7 2 10 1 2 1 2 4 0 4 5 2 2 3 2 3 4 1 3 5 2 1 5 3 2 2 0 10 1 2 0 2 1 0 Output: 3 -1 My Output: 3 1 Code:

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