82分，不是最短路的问题，求大佬帮忙康康

第6和9个点错了，DIJ和SPFA都是82分

#include<bits/stdc++.h>
using namespace std;
struct as{
	long long v,w;
};
struct node{
	long long u,d;
	bool operator<(const node&rsh)const{
		return d>rsh.d;
	} 
};
long long t;
long long n,m,k,p;
vector<as>G[100001];
vector<as>F[100001];
long long dis[100001];
bool visgu[100001];
namespace DPKJ{
	bool vis[100001][55];
	long long f[100001][55];
	void cleanit(){
		memset(f,-1,sizeof(f));
	}
	long long dp(long long x,long long l){
		if(l<0||l>k)return 0;
		if(vis[x][l]){
			vis[x][l]=0;
			return -1;
		}
		if(f[x][l]!=-1){
			return f[x][l];
		}
		vis[x][l]=1;
		long long ans=0;
		for(long long i=0;i<F[x].size();i++){
			as gu=F[x][i];
			long long v=gu.v,w=gu.w;
			long long ned=dp(v,dis[x]-dis[v]-w+l);
			if(ned!=-1){
				ans=(ans%p+ned%p)%p;
			}else{
				return -1;
			}
		}
		if(x==1&&l==0)ans++;
		f[x][l]=ans;
		vis[x][l]=0;
		return ans;
	}
}
void add(long long u,long long v,long long w){
	G[u].push_back((as){
		v,w
	});
	F[v].push_back((as){
		u,w
	});
}
void cls(){
	for(long long i=1;i<=n;i++){
		G[i].clear();
		F[i].clear();
		dis[i]=0x3f3f3f3f;
		visgu[i]=0;
	}
}
void DIJ(){
	priority_queue<node>q;
	q.push((node){
		1,0	
	});
	dis[1]=0;
	while(!q.empty()){
		node gu=q.top();q.pop();
		long long u=gu.u,d=gu.d;
		if(dis[u]!=d)continue;
		for(long long i=0;i<G[u].size();i++){
			as gugu=G[u][i];
			long long v=gugu.v,w=gugu.w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push((node){
					v,dis[v]
				}) ;
			}
		}
	} 
}
void SPFA(){
	int q[1000001],t=0,w=0;
	q[t++]=1;
	dis[1]=0;
	while(t-w>0){
		int u=q[w++];
		for(int i=0;i<G[u].size();i++){
			as gu=G[u][i];
			int v=gu.v,w=gu.w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q[t++]=v;
			}
		}
	}
}
long long willtodo(){
	scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
	cls();
	for(long long i=1;i<=m;i++){
		long long t1,t2,t3;
		scanf("%lld%lld%lld",&t1,&t2,&t3);
		add(t1,t2,t3); 
	}
//	DIJ();
	SPFA();
	DPKJ::cleanit();
	long long ans=0;
	for(long long i=0;i<=k;i++){
		long long ned=DPKJ::dp(n,i);
		if(ned!=-1){
			ans=(ans%p+ned%p)%p;
		}else{
			return -1;
		}
	}
	return ans;
}
int main(){
	scanf("%lld",&t);
	while(t--)printf("%lld\n",willtodo());
    return 0;
}
/*
1
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
*/