#include<bits/stdc++.h>
#define maxn 1001
#define maxm 2001
using namespace std;
typedef struct{
	int next;
	int to;
	int co;
}Edge;
Edge edge[maxm];
int n,m,k,p,t,a,b,c,d,cnt,ans,head[maxm],book[maxn],nums,ways,lown;
inline char getc()
{
    static char buf[1<<18], *fs, *fe;
    return (fs == fe && (fe = (fs = buf)+fread(buf, 1, 1<<18, stdin)), fs == fe)? EOF: *fs++;
}
int read()
{
    int x = 0, flag = 1;
    char ch;
    ch = getc();
    while(ch<'0' || ch>'9')
    {
        if(ch == '-')
            flag = -1;
        ch = getc();
    }
    while(ch>='0' && ch<='9')
    {
        x = x*10+ch-'0';
        ch = getc();
    }
    return x*flag;
}
void add(int from,int to,int co){
	edge[++cnt].next = head[from];
	edge[cnt].to=to;
	edge[cnt].co=co;
	head[from]=cnt;
}
void DFS(int start,int state,int tag){
	for(int i=head[start];i;i=edge[i].next){
		//cout<<"i="<<i<<endl; 
		if(!book[edge[i].to]){
			book[edge[i].to]=1;
			nums+=edge[i].co;			
			//cout<<"to="<<edge[i].to<<endl;
			if(edge[i].to==n){
				if(tag==1){
					lown=min(nums,lown);
					ways++;
				}
				if(tag==2){
					if(nums<=lown+k)ans++;
				}
				//cout<<"state="<<state<<" nums="<<rail[state]<<endl;
				//return;
			}else DFS(edge[i].to,state+(1<<edge[i].to),tag);
			//cout<<"hs"<<endl;
			book[edge[i].to]=0;
			nums-=edge[i].co;
		}
	} 
	//return;
} 
int Makico(){
	freopen("2017park.in","r",stdin);
	freopen("2017park.out","w",stdout);	
	t=read();
	for(int i=1;i<=t;i++){
		memset(head,0,sizeof(head));
		memset(book,0,sizeof(book));
		memset(edge,0,sizeof(edge));
		cnt=ans=nums=ways=0;
		lown=9999;
		n=read();m=read();k=read();p=read();
		for(int i=1;i<=m;i++){
			a=read();b=read();c=read();
			add(a,b,c);
	 	}
		book[1]=1;
		DFS(1,1,1);
		DFS(1,1,2);
		if(ans)cout<<ans%p<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}
int God = Makico();
int main(){;}