RT,按照题解的思路，

第一份代码用链式前向星写，只拿了64分 ，剩下的TLE

第二份用vector写才满分，

求大佬指点迷津

//链式前向星版
#include<bits/stdc++.h>
using namespace std;
queue <int> q;
int tot1,next1[210001],to1[210001],val1[210001],poi1[210001];
int tot2,next2[210001],to2[210001],val2[210001],poi2[210001];
int dis[210001],f[210001][51],mod,k;
bool flag[210001][51];
inline void add1(int x,int y,int z){
	tot1++;
	next1[tot1]=poi1[x];poi1[x]=tot1;to1[tot1]=y;val1[tot1]=z;
}
inline void add2(int x,int y,int z){
	tot2++;
	next2[tot2]=poi2[x];poi2[x]=tot2;to2[tot2]=y;val2[tot2]=z;
}
inline void SPFA(){
	memset(dis,0x3f,sizeof(dis));
	q.push(1);dis[1]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(register int e=poi1[x];e;e=next1[e]){
			if(dis[to1[e]]>dis[x]+val1[e]){
				dis[to1[e]]=dis[x]+val1[e];
				q.push(to1[e]);
			}
		}
	}
}
inline int dfs(int x,int l){
	if(l<0 or l>k)return 0;
	if(flag[x][l]){
		flag[x][l]=0;
	    return -1;
	}
	
	if(f[x][l]!=-1)return f[x][l];
	int re=0;
	flag[x][l]=1;
	for(register int e=poi2[x];e;e=next2[e]){
		int ls=dfs(to2[e],dis[x]-dis[to2[e]]+l-val2[e]);
		if(ls==-1){
			flag[x][l]=0;
		    return -1;
		}
		re+=ls;
		re%=mod;
	}
	flag[x][l]=0;
	if(x==1 and l==0)re++;
	f[x][l]=re;
	return re;
}
inline int read(){
	char c=getchar();
	int s=0,f=1;
	while(c<'0' or c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0' and c<='9'){
		s=(s<<1)+(s<<3)+c-'0';
		c=getchar();
	}
	return s*f;
}
int main(){
	int T,n,m,a,b,c;
	T=read();
	while(T--){
		memset(f,-1,sizeof(f));
		memset(poi1,0,sizeof(poi1));
		memset(poi2,0,sizeof(poi2));
		memset(next1,0,sizeof(next1));
		memset(next2,0,sizeof(next2));
		n=read();m=read();k=read();mod=read();
		for(register int i=1;i<=m;i++){
			a=read();b=read();c=read();
			add1(a,b,c);
			add2(b,a,c);
		}
		SPFA();
		int ans=0;
		bool flag=0;
		for(register int i=0;i<=k;i++){
			int ls=dfs(n,i);
			if(ls==-1){
				printf("-1\n");
				flag=1;
			    break;
			}
			ans+=ls;
			ans%=mod;
	    }
	    if(!flag)
	    printf("%d\n",ans);
	}
    return 0;
}

//vector版本
#include<bits/stdc++.h>
using namespace std;
queue <int> q;
struct node  {
    int to,val;
};
vector<node>poi1[110001];
vector<node>poi2[110001];
int dis[210001],f[210001][51],mod,k;
bool flag[210001][51];
inline void SPFA(){
	memset(dis,0x3f,sizeof(dis));
	q.push(1);dis[1]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(register int e=0;e<poi1[x].size();e++){
			if(dis[poi1[x][e].to]>dis[x]+poi1[x][e].val){
				dis[poi1[x][e].to]=dis[x]+poi1[x][e].val;
				q.push(poi1[x][e].to);
			}
		}
	}
}
inline int dfs(int x,int l){
	if(l<0 or l>k)return 0;
	if(flag[x][l]){
		flag[x][l]=0;
	    return -1;
	}
	if(f[x][l]!=-1)return f[x][l];
	int re=0;
	flag[x][l]=1;
	for(register int e=0;e<poi2[x].size();e++){
		int ls=dfs(poi2[x][e].to,dis[x]-dis[poi2[x][e].to]+l-poi2[x][e].val);
		if(ls==-1){
			flag[x][l]=0;
		    return -1;
		}
		re+=ls;
		re%=mod;
	}
	flag[x][l]=0;
	if(x==1 and l==0)re++;
	f[x][l]=re;
	return re;
}
inline int read(){
	char c=getchar();
	int s=0,f=1;
	while(c<'0' or c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0' and c<='9'){
		s=(s<<1)+(s<<3)+c-'0';
		c=getchar();
	}
	return s*f;
}
inline void get(int m){
	int a,b,c;
	for(register int i=1;i<=m;i++){
			a=read();b=read();c=read();
			node  e;
        e.to=b;	e.val=c;
        poi1[a].push_back(e);
        e.to=a;				
        poi2[b].push_back(e);
	}
}
inline void work(){
	int n,m;
	memset(f,-1,sizeof(f));
	for(register int i=1;i<=n;i++){
		poi1[i].clear();
		poi2[i].clear();
	}
		n=read();m=read();k=read();mod=read();
		get(m);
		SPFA();
		int ans=0;
		bool flag=0;
		for(register int i=0;i<=k;i++){
			int ls=dfs(n,i);
			if(ls==-1){
				printf("-1\n");
				flag=1;
			    break;
			}
			ans+=ls;
			ans%=mod;
	    }
	    if(!flag)
	    printf("%d\n",ans);
}
int main(){
	int T;
	T=read();
	while(T--){
		work();
	}
    return 0;
}