可以过所有小 hack 数据
不知道哪里写挂了/ll

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
const int maxn = 1e5;

struct side {
	int l, to;
};
inline int operator < (const side &a, const side &b) {
	return a.l > b.l;
}
std :: vector <side> S[maxn + 10];
std :: vector <int> S0[maxn + 10], SS[maxn + 10], con[maxn + 10];

std :: priority_queue <side> Q;

std :: queue <int> P;

int T, n, m, k, p, u, v, w, d[maxn + 10], vis[maxn + 10];
long long dp[maxn + 10][60];
int len, real[maxn + 10], in[maxn + 10];

inline void dij() {
	for (int i = 2; i <= n; i++)
		d[i] = 2100000000;
	for (int i = 1; i <= n; i++)
		vis[i] = 0;
	while (!Q.empty()) Q.pop();
	Q.push({0, 1});
	while (!Q.empty()) {
		side now = Q.top(); Q.pop();
		if (vis[now.to]) continue;
		vis[now.to] = 1;
		for (side i : S[now.to])
			if (d[i.to] > d[now.to] + i.l)
				Q.push({d[i.to] = d[now.to] + i.l, i.to});
	}
//	for (int i = 1; i <= n; i++)
//		printf("%d ", d[i]);
//	putchar('\n');
	
	return;
}

int mytimer, dfn[maxn + 10], low[maxn + 10], stac[maxn + 10], h;
int siz[maxn + 10], to[maxn + 10], inf[maxn + 10][60], reinf[maxn + 10][60];

void dfs(int i) {
	if (dfn[i]) return;
	stac[++h] = i;
	dfn[i] = low[i] = ++mytimer;
	for (int j : S0[i])
		if (dfn[j] && !to[j]) low[i] = std :: min(low[i], low[j]);
		else if (!to[j]) dfs(j), low[i] = std :: min(low[i], low[j]);
	
//	printf("i = %d\n", i);
//	putchar('\n');
//	for (int i = 1; i <= h; i++)
//		printf("%d %d %d\n", stac[i], dfn[stac[i]], low[stac[i]]);
//	putchar('\n');
	if (low[i] == dfn[i]) {
		len++;
		while (stac[h] != i) {
			to[stac[h]] = len;
			con[len].push_back(stac[h]);
			siz[len]++;
			h--;
		}
		h--;
		to[i] = len;
		con[len].push_back(i);
		siz[len]++;
		for (int j : con[len]) 
			for (int l = 0; l <= k; l++)
				inf[j][l] = (siz[len] > 1);
	}
	
	return;
}

int main(void) {
	//freopen("in.in", "r", stdin);
	//freopen("out.out", "w", stdout);
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d %d", &n, &m, &k, &p);
		mytimer = h = 0;
		for (int i = 1; i <= n; i++)
			dfn[i] = 0;
		for (int i = 1; i <= n; i++)
			low[i] = 0;
		for (int i = 1; i <= n; i++)
			siz[i] = 0;
		for (int i = 1; i <= n; i++)
			in[i] = 0;
		for (int i = 1; i <= n; i++)
			to[i] = 0;
		for (int i = 1; i <= n; i++)
			con[i].clear();
		for (int i = 1; i <= n; i++)
			S[i].clear();
		for (int i = 1; i <= n; i++)
			S0[i].clear();
		for (int i = 1; i <= n; i++)
			SS[i].clear();
		for (int i = 1; i <= n; i++)
			for (int j = 0; j <= k; j++)
				inf[i][j] = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 0; j <= k; j++)
				reinf[i][j] = 0;
		while (m--) {
			scanf("%d %d %d", &u, &v, &w);
			S[u].push_back({w, v});
			if (!w) S0[u].push_back(v);
		}
		dij();
		
		len = 0;
		for (int i = 1; i <= n; i++)
			dfs(i);
		for (int i = 1; i <= n; i++)
			for (int j : S0[i])
				if (to[i] != to[j])
					SS[to[i]].push_back(to[j]), in[to[j]]++;
//		printf("P.size() = %d\n", P.size());
//		printf("%d\n", len);
//		for (int i = 1; i <= n; i++)
//			printf("%d %d %d %d\n", dfn[i], low[i], to[i], con[i].size());
		mytimer = 0;
		while (!P.empty()) P.pop();
		for (int i = 1; i <= len; i++)
			if (!in[i]) {
				P.push(i);
				for (int j : con[i])
					real[++mytimer] = j;
			}
		while (!P.empty()) {
			int now = P.front(); P.pop();
			for (int i : SS[now]) {
//				printf("i = %d\n", i);
				in[i]--;
				if (!in[i]) {
					for (int j : con[i])
						real[++mytimer] = j;
					P.push(i);
				}
			}
		}
//		for (int i = 1; i <= n; i++)
//			printf("%d ", real[i]);
//		putchar('\n');
		
		for (int i = 0; i <= k; i++)
			for (int j = 1; j <= n; j++)
				dp[j][i] = 0;
		dp[1][0] = 1;
		reinf[1][0] = 1;
		for (int i = 0; i <= k; i++) {
			for (int j = 1; j <= n; j++)
				for (side l : S[real[j]]) 
					if (d[real[j]] + l.l + i <= k + d[l.to]) {
						int las = d[real[j]] + l.l + i - d[l.to];
						(dp[l.to][las] += dp[real[j]][i]) %= p;
						if (reinf[real[j]]) {
							reinf[l.to][las] = 1;
							inf[l.to][las] |= inf[real[j]][i];
						}
					}
		} 
//		for (int i = 1; i <= n; i++, putchar('\n'))
//			for (int j = 0; j <= k; j++)
//				printf("%lld ", dp[i][j]); 
		long long sum = 0, kil = 0;
		for (int i = 0; i <= k; i++) {
			(sum += dp[n][i]) %= p;
			kil |= inf[n][i];
		}
		printf("%lld\n", kil ? -1 : sum);
	}
    
    return 0;
}