本人太久没做紫题了，所以想不看题解做出这道题，然而怎么调都对不了。

基本思路：先dij跑反向图求出每个点到n的最短路长，接着tarjan求强连通分量判0环，然后用记忆化搜索，cnt[n][rest]表示对于点n，它到终点路径长比从此点的最短路长度大rest的路径总数，然后记忆化搜索。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 1e5+10;
int n,m,a[N];
int f[N];
int cnt[N][55];
int dis[N];
bool vis[N];
int dis2[N];
int pre[N],low[N],dfn;
int stk[N],top,scc,sccno[N];
int sccflag[N];
int k,p;
struct node{
	int v,w;
	bool operator>(const node &a) const {return w>a.w;}
};
vector<node> vec[N];
vector<node> opp[N];
int t;

inline void tar(int x){
	pre[x] = low[x] = ++dfn;
	stk[++top] = x;
	for(int i=0;i<vec[x].size();i++){
		int v = vec[x][i].v;
		if(!pre[v]){
			tar(v);
			low[x] = min(low[x],low[v]);
		}
		else if(!sccno[v]){
			low[x] = min(low[x],pre[v]);
		}
	}
	if(pre[x]==low[x]){
		++scc;
		for(;;){
			int u = stk[top--];
			sccno[u] = scc;
			if(x==u) break;
		}
	}
}

inline void dij(int x){
	priority_queue<node,vector<node>,greater<node> > q;
	dis[x] = 0;
	q.push({x,0});
	while(!q.empty()){
		int u = q.top().v;q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		if(u==1) continue;
		for(int i=0;i<opp[u].size();i++){
			int v = opp[u][i].v,w = opp[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v] = dis[u]+w;
				q.push({v,dis[v]});
			}
		}
	}
}

inline int search(int x,int rest){
	if(rest<0 || rest>50) return 0;
	if(cnt[x][rest]!=-1) return cnt[x][rest];
	for(int i=0;i<vec[x].size();i++){
		int v = vec[x][i].v,w = vec[x][i].w;
		if(dis[x]-dis[v]+rest-w>=0 && dis[x]-dis[v]+rest-w<=50){
			cnt[x][rest] = (cnt[x][rest]+search(v,dis[x]-dis[v]+rest-w))%p;
		}
	}
	cnt[x][rest]++;
	return cnt[x][rest];
}

signed main(){
	ios::sync_with_stdio(false);
	cin>>t;
	int q1,q2,q3;
	while(t--){
		cin>>n>>m>>k>>p;
		
		scc = dfn = top = 0;
		for(int i=1;i<=n;i++){
			vec[i].clear();
			opp[i].clear();
			dis[i] = 0x3f3f3f3f;
			vis[i] = 0;
			dis2[i] = 0;
			pre[i] = 0;
			low[i] = 0;
			sccno[i] = 0;
			sccflag[i] = -1;
			for(int j=0;j<=50;j++){
				cnt[i][j] = -1;
			}
		}
		
		for(int i=1;i<=m;i++){
			cin>>q1>>q2>>q3;
			vec[q1].push_back({q2,q3});
			opp[q2].push_back({q1,q3});
		}
		/*if(p==10){
			cout<<-1<<endl;
			continue;
		}*/
			
		dij(n);
		tar(1);
		for(int i=1;i<=n;i++){
			//cout<<i<<' '<<sccno[i]<<endl;
			if(dis[i]==0x3f3f3f3f) continue;
			for(int j=0;j<vec[i].size();j++){
				int v = vec[i][j].v,w = vec[i][j].w;
				if(sccno[i]==sccno[v]){
					//cout<<333;
					if(w==0){
						if(sccflag[i]==-1) sccflag[i] = 0;
					}
					else{
						sccflag[i] = 1;
					}
				}
			}
		}
		bool flag =  0;
		for(int i=1;i<=scc;i++){
			if(sccflag[i]==0){
				//cout<<i<<endl;
				cout<<-1<<endl;
				flag = 1;
				break;
			}
		}
		if(flag) continue;
		
		/*if(dfs(1,1)){
			cout<<-1<<endl;
			continue;
		}*/
		for(int i=0;i<=50;i++){
			cnt[n][i] = 1;
		}
		cout<<search(1,k)<<endl;
	}
	
	return 0;
}