#include <bits/stdc++.h>
using namespace std;
struct edge{
	int to, nxt;
	int value;
}e[200001];
stack<int> s, s1;
vector<int> r[100001], pic[100001], ord;
long long ways[51][100001], P, ans;
int head[100001], dis[100001], dfn[100001], low[100001], vis[100001], node[100001], into[100001], T, N, M, K, tot;
void dijkstra(long long w[], int s){
	priority_queue<pair<int, int> > pq; pair<int, int> t;
	for(int i=1; i<=N; i++){dis[i]=-1; w[i]=0;} dis[s]=0; w[s]=1;
	pq.push(make_pair(0, s));
	while(!pq.empty()){
		t=pq.top(); pq.pop();
		int p=t.second;
		if(dis[p]+t.first){continue;}
		for(int i=head[p]; i; i=e[i].nxt){
			if(dis[e[i].to]<0||dis[p]+e[i].value<dis[e[i].to]){
				int np=e[i].to;
				dis[np]=dis[p]+e[i].value;
				pq.push(make_pair(-1*dis[np], np));
				w[np]=w[p]; w[np]%=P;
			}else if(dis[p]+e[i].value==dis[e[i].to]){
				w[e[i].to]+=w[p]; w[e[i].to]%=P;
			}
		}
	}
	for(int i=1; i<=N; i++){
		r[i].clear();
		for(int j=head[i]; j; j=e[j].nxt){
			if(dis[i]+e[j].value==dis[e[j].to]){
				r[i].push_back(e[j].to);
			}
		}
	}
}
void Tarjan(int x){
	dfn[x]=low[x]=++tot;
	s.push(x); vis[x]=1;
	for(int i=0; i<r[x].size(); i++){
		if(!dfn[r[x][i]]){
			Tarjan(r[x][i]);
			low[x]=min(low[x], dfn[r[x][i]]);
		}else if(vis[r[x][i]]){
			low[x]=min(low[x], dfn[r[x][i]]);
		}
	}
	int now=0, num=0;
	if(dfn[x]==low[x]){
		while(now!=x){
			now=s.top(); s.pop();
			s1.push(now);
			vis[now]=0;
		}
		if(s1.size()>1){
			while(!s1.empty()){
				now=s1.top(); s1.pop();
				node[now]=x;
				ways[0][now]=-1;
			}
		}else{
			s1.pop();
		}
	}
}
void build(){
	for(int i=1; i<=N; i++){
		if(!node[i]){node[i]=i;}
	}
	for(int i=1; i<=N; i++){
		for(int j=0; j<r[i].size(); j++){
			int x=node[i], y=node[r[i][j]];
			pic[x].push_back(y); into[y]++;
		}
	}
}
void tp(){
	queue<int> q; q.push(1);
	while(!q.empty()){
		int x=q.front(); q.pop();
		ord.push_back(x);
		for(int i=0; i<pic[x].size(); i++){
			into[pic[x][i]]--;
			if(!into[pic[x][i]]){
				q.push(pic[x][i]);
			}
		}
	}
}
void solve(){
	if(ways[0][N]<0){ans=-1; return;}
	else{ans=ways[0][N];}
	for(int i=1; i<=K; i++){
		for(int j=1; j<=N; j++){
			for(int k=head[j]; k; k=e[k].nxt){
				if(ways[i][node[e[k].to]]<0){continue;}
				int l=dis[e[k].to]+i-dis[j]-e[k].value;
				if(l<0||(l>=i)){continue;}
				if(ways[l][node[j]]<0){
					ways[i][node[e[k].to]]=-1;
					continue;
				}
				ways[i][node[e[k].to]]+=ways[l][node[j]];
				ways[i][node[e[k].to]]%=P;
			}
		}
		for(int j=0; j<ord.size(); j++){
			for(int k=0; k<pic[ord[j]].size(); k++){
				if(ways[i][pic[ord[j]][k]]<0){continue;}
				if(ways[i][ord[j]]<0){ways[i][pic[ord[j]][k]]=-1;}
				else{
					ways[i][pic[ord[j]][k]]+=ways[i][ord[j]];
					ways[i][pic[ord[j]][k]]%=P;
				}
			}
		}
		if(ways[i][N]<0){ans=-1; return;}
		else{ans+=ways[i][N]; ans%=P;}
	}
}
void reset(){
	for(int i=1; i<=N; i++){head[i]=0;}
	for(int i=1; i<=N; i++){
		pic[i].clear();
		node[i]=dfn[i]=low[i]=0;
		for(int j=1; j<=K; j++){
			ways[j][i]=0;
		}
		ord.clear();
		tot=0;
	}
}
void run(){
	dijkstra(ways[0], 1);
	Tarjan(1); build();
	tp(); solve();
	reset();
}
int main(){
	scanf("%d", &T);
	for(int u=1; u<=T; u++){
		ans=0;
		scanf("%d%d%d%d", &N, &M, &K, &P);
		for(int a, b, c, i=1; i<=M; i++){
			scanf("%d%d%d", &a, &b, &c);
			e[i].to=b; e[i].nxt=head[a]; head[a]=i; e[i].value=c;
		}
		run();
		printf("%lld\n", ans);
	}
	return 0;
}

WA on #8 #9 #11 #12 #13