rt

#include <bits/stdc++.h>
#define maxn 300100
using namespace std;
const int inf = 2147483647;
//const int mod = 
struct EDGE {
	int to,nxt,w;
} e[maxn * 2],e2[maxn * 2];
int head[maxn * 2],head2[maxn * 2];
int T;
int cnt = 0;
int n,m,k,p;
inline void add(int a,int b,int c) {
	e[++cnt].to = b;
	e[cnt].w = c;
	e[cnt].nxt = head[a];
	head[a] = cnt;
}
int cnt2 = 0;
inline void add2(int a,int b,int c) {
	e2[++cnt2].to = b;
	e2[cnt2].w = c;
	e2[cnt2].nxt = head2[a];
	head2[a] = cnt2;
}

int f[maxn * 2][105]; //记忆化数组 
bool vis[maxn * 2];
int dis[maxn * 2];

struct node {
	int v,w;
	friend bool operator < (node a,node b) {
		return a.w > b.w;
	}
} tmp;
priority_queue<node> q;
int s = n;
bool vis2[maxn * 2][105];
inline void init() {
	memset(head,0,sizeof head);
	memset(vis,false,sizeof vis);
	memset(vis2,false,sizeof vis2);
	memset(f,0,sizeof f);
	memset(head2,0,sizeof head2);	
	cnt = 0,cnt2 = 0;
	while(!q.empty()) q.pop();
}

inline void dijstra() {
	s = n;
	for(int i = 1; i <= n; i++) dis[i] = inf;
	dis[s] = 0;
	tmp.v = s;
	tmp.w = 0;
	q.push(tmp);
	while(!q.empty()) {
		int u = q.top().v;
		q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(int i = head2[u]; i; i = e2[i].nxt) {
			int v = e2[i].to;
			if(dis[v] > (long long) dis[u] + e2[i].w) {
				dis[v] = dis[u] + e2[i].w;
				tmp.w = dis[v];
				tmp.v = v;
				q.push(tmp);
			}
		}
	}
}

inline int dfs(int x,int j) {
	if(vis2[x][j]) return -1;
	if(f[x][j]) return f[x][j];
	vis2[x][j] = 1;
	if(x == n) f[x][j] = 1;
	for(int i = head[x]; i; i = e[i].nxt){
		int v = e[i].to;
		int tmp = j + dis[x] - dis[v] - e[i].w;
		if(tmp >= 0){
			if(dfs(v,tmp) == -1) return -1;
			f[x][j] = (f[x][j] + dfs(v,tmp)) % p;
		}
	}
	vis2[x][j] = 0;
	return f[x][j];
}
/*
1.无穷多条如何判断
2.记搜怎么写 
*/
int u,v,w;
int main() {
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	scanf("%d",&T);
	while(T--) {
		scanf("%d %d %d %d",&n,&m,&k,&p);
		for(int i = 1; i <= m; i++) {
			scanf("%d %d %d",&u,&v,&w);
			add(u,v,w);
			add2(v,u,w);
		}
		s = n;
		dijstra();
		cout << dfs(1,k) << endl; 
		init();
	}
	return 0;
}