70pts

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n, m, k, p;
const int N = 2e5 + 5, M = 1e5 + 5;
vector<pair<int, int> > Adj[N], Adj2[N];
int dis[M];
bool vis[M];
inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -1; ch=getchar();}
	while (isdigit(ch)) {x = (x << 1) + (x << 3) + (ch ^ 48); ch=getchar();}
	return x * f;
}
inline void print(int x){
	if(x < 0) print('-'), x = -x;
	if (x >= 10) print(x / 10);
	putchar(x % 10 + '0'); 
}
priority_queue<pair<int, int> > q;
void dij() {
	memset(dis, 0x3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[n] = 0;
	q.push(make_pair(-dis[n], n));
	while (!q.empty()) {
		pair<int, int> Tmp = q.top();
		q.pop();
		int u = Tmp.second;
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto tmp : Adj[u]) {
			int v = tmp.first, w = tmp.second;
			if (!vis[v] && dis[u] + w <= dis[v]) {
				dis[v] = dis[u] + w;
				q.push(make_pair(-dis[v], v));
			}
		} 
	} 
}
int dp[M][51];
int flag[M][51];
bool check = false;
int dfs(int x, int now) {
	if (now < 0) return 0;
	if (flag[x][now] == 1) {
		check = true;
		return 0;
	}
	if (dp[x][now]) return dp[x][now];
	int ans = 0;
	flag[x][now] = 1;
	for (auto tmp : Adj2[x]) {
		int v = tmp.first, w = tmp.second;
		ans = (ans + dfs(v, now - (dis[v] + w - dis[x])) % p) % p;
		if (check) return 0;
	}
	if (x == n && now == 0) ans = 1;
	flag[x][now] = 0;
	return dp[x][now] = ans;
}
signed main() {
	t = read();
	while (t--) {
		memset(dp, 0, sizeof dp);
		check = false;
		n = read(), m = read(), k = read(), p = read(); 
		for (int i = 1; i <= m; i++) {
			int a, b, c;
			a = read(), b = read(), c = read();
			Adj2[a].push_back(make_pair(b, c));
			Adj[b].push_back(make_pair(a, c));
		}
		dij();
		int ans = 0;
		for (int i = 0; i <= k; i++) {
			memset(flag, 0, sizeof flag);
			ans = (ans + dfs(1, i) % p) % p;
		}
		if (check) puts("-1");
		else print(ans), puts("");
		for (int i = 1; i <= n; i++) Adj[i].clear(), Adj2[i].clear();
	}
	return 0;
}