​ 为什么要topo排序呢？辣么判断复杂而且还容易出锅qwq（我太菜了）

​ 直接上tarjan就好了啊！

​ 这道题还是比较简单的，不过，如果我们dp方程没设好的话，在某些网站上就容易被卡（比如只有128MB的空间限制）

​ 我们观察题目，发现题目的K值很小，最大也就50，于是，我们可以从K值入手。

​ 我们设dp(i,j)表示我们走到i号点，此时与最短路的“偏差值为j”的方案数

​ 由于dp太烦，所以我选择记搜

​ 我们先用dijkstra跑出1到每个点的最短路，设为dis[i]

​ 然后我们就来记搜。如果我们到达了n号点，我们就将现在的答案加一，但注意，不要直接return，因为我们可以先跑到n号点然后再乱跑一波后又跑到n号点，这也可能成为一种方案。

​ 转移的话，令下一个为v，我们只需要计算"偏差值"即可，我们发现，我们要是从x到达了v的话，这一段产生的偏差与之前的无关，所以，就只需要看我们从x到v和1到v的最短路产生了多少偏差即可，即是:dis[x]+w-dis[v]

​ 这样，跑一波简单的记搜，就可以拿到70分了~

​ 然鹅，我们接下来还需要判断，是否有无限种方案。

​ 什么情况会产生无限种方案呢？

​ 很明显的，当一个可行的方案中存在0环的时候，肯定就可以相应的产生出无限种方案了

​ 于是，我们可以先对于边权为0的边所组成的图跑一遍tarjan。

​ 然后，我们观察是否有一种可行的方案通过了0环，如果有，输出-1即可。

​ 代码(由于有一部分是以前写的，所以有点丑，还请见谅)：

#pragma GCC optimize(3,"inline","Ofast")//手动O3优化
#include<bits/stdc++.h>
using namespace std;
const int N=100001,P=5139222;
int n,m,k,p;
struct ver{
    int u,v,w,next;
}t[N<<1];
priority_queue<pair<int,int> >s;
int las[N],resav[N];
int dis[N],d;
bool vis[N];
int tot;
inline void add(int u,int v,int w){
    tot++;
    t[tot].u=u,t[tot].v=v,t[tot].w=w;
    t[tot].next=las[u],las[u]=tot;
    return;
}
inline void dij(){
    vis[1]=dis[1]=0;
    s.push(make_pair(0,1));
    while(!s.empty()){
        int x=s.top().second,y=s.top().first;
        s.pop();
        if(vis[x]){
            continue;
        }
        vis[x]=1;
        for(int i=las[x];i;i=t[i].next){
            int v=t[i].v,w=t[i].w;
            if(dis[v]>dis[x]+w){
                dis[v]=dis[x]+w;
                s.push(make_pair(-dis[v],v));
            }
        }
    }
}
int ans;int fa[N],sta[N],top,low[N],dfn[N];
int ji[N][51],cnt,tol[N];
bool vist[N][51],ip[N];
inline void Add(int x,int y){
	q[++len]=(ver){x,y,0,pas[x]},pas[x]=len;
}
bool F;
inline int dfs(int x,int y){
    if(y>k){
        return 0;
    }
    if(vist[x][y]){//记忆化搜索
        return ji[x][y];
    }
    vist[x][y]=1;
    ji[x][y]=0;
    if(x==n){
        ji[x][y]++;
    }
    for(int i=las[x];i;i=t[i].next){
        int nowp=dfs(t[i].v,y+(dis[x]+t[i].w-dis[t[i].v]));
        if(nowp&&tol[fa[t[i].v]]>1){//判断是否有一种方案通过了零环
        	F=1;
        	return 0;
		}
		ji[x][y]+=nowp;
		ji[x][y]%=p;
    }
    ji[x][y]%=p;
    return ji[x][y];
}
inline void tarjan(int x){//tarjan
	dfn[x]=low[x]=++cnt;sta[++top]=x;ip[x]=1;
	for(int i=las[x];i;i=t[i].next){
		if(t[i].w){
			continue;
		}
		int v=t[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else if(ip[v]){
			low[x]=min(low[x],dfn[v]);
		}
	}
	if(low[x]==dfn[x]){
		while(true){
			int v=sta[top--];
			ip[v]=0;fa[v]=x;++tol[x];
			if(v==x){
				break;
			}
		}
	}
}
inline void check(){
	cnt=0;
	for(int i=1;i<=n;++i){
		dfn[i]=low[i]=0,fa[i]=i,tol[i]=0;
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			tarjan(i);
		}
	}
}
inline int read(){//fast read for int
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
int main(){
    int T;
    T=read();
    bool flag=1;
    while(T--){
        ans=0;
        n=read(),m=read(),k=read(),p=read();
        las[1]=0;F=0;memset(pas,0,sizeof(pas)),len=0;
        for(int i=2;i<=n;++i){
            las[i]=0,dis[i]=P;
            vis[i]=0;
        }
        tot=0;
        for(int i=1;i<=m;++i){
            int x,y,w;
            x=read(),y=read(),w=read();
            add(x,y,w);
        }
        check();
		dij();
        int rep=dfs(1,0)%p;
        if(F){
        	puts("-1");
		}else{
			printf("%d\n",rep);
		}
        if(!T){
            break;
        }
        memset(vist,0,sizeof(vist));
    }
    return 0;
}