#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

struct node
{
	int to,w,next;
};
const int N=100000+5,M=200000+5;
int n,m,K,mm,h[N],len;
node e[M];

int d[N],f[N][51],ans;
bool used[N][51];

template<class T>
inline void Read(T &x)
{
	char ch;
	while(ch=getchar(),ch<'0' || ch>'9'); x=ch-'0';
	while(ch=getchar(),ch>='0' && ch<='9') x=x*10+ch-'0';
}
inline void Add(int i, int j, int w)//建图 
{
	len++; e[len].to=j; e[len].w=w; e[len].next=h[i]; h[i]=len;
}
int h2[N],len2;
node e2[M];
inline void Add2(int i, int j, int w)//建反图 
{
	len2++; e2[len2].to=j; e2[len2].w=w; e2[len2].next=h2[i]; h2[i]=len2;
}
void init()
{
	memset(h,-1,sizeof(h)); memset(e,-1,sizeof(e)); len=0;
	memset(h2,-1,sizeof(h2)); memset(e2,-1,sizeof(e2)); len2=0;
	Read(n); Read(m); Read(K); Read(mm);
	for (int k=0; k<m; k++)
	{
		int i,j,w; Read(i); Read(j); Read(w); Add(i,j,w); Add2(j,i,w);
	}
}
int tdp(int u, int left)//u表示当前点，left表示当前的k还有多少剩余
{
    if (left<0 || left>K) return 0;
    if (used[u][left])
	{
        used[u][left]=false;//出现0环：路径长度不变，又回到当前点 
        return -1;
    }
    if(f[u][left]!=-1) return f[u][left];//记忆化 
    
    int ret=0; used[u][left]=true;//出现过当前状态 
    for (int i=h2[u]; ~i; i=e2[i].next)//搜索反图 
    {
    	int v=e2[i].to;
    	int t=tdp(v,(d[u]+left-e2[i].w)-d[v]);//d[u]+left-e2[i].w就是到v的最长距离，减去d[v]，就是机动长度 

        if (t==-1)
		{
            used[u][left]=false;
            return -1;
        }
        ret=(ret+t)%mm;
    }
    used[u][left]=false;
    
    if (u==1 && left==0) ret++;
    f[u][left]=ret;//f[i][j]表示从n到i的距离<=最短距离+j 的方案数 
    
    return ret;
}
int front,tail,q[N];
bool visited[N];
void spfa()//求出d数组：d[i]表示1到结点i的最短距离 
{
	memset(d,0x3f,sizeof(d)); memset(visited,false,sizeof(visited));
    front=0; tail=1; q[tail]=1; d[1]=0; visited[1]=true;
    while(front!=tail)
    {
    	front=(front+1)%n;
    	int u=q[front]; visited[u]=false;
    	for (int i=h[u]; ~i; i=e[i].next)
    	{
    		int v=e[i].to;
    		if (d[v]>d[u]+e[i].w)
    		{
    			d[v]=d[u]+e[i].w;
    			if (!visited[v])
    			{
    				tail=(tail+1)%n; q[tail]=v; visited[v]=true;
				}
			}
		}
	}
}
void work()
{
    spfa();
    ans=0; memset(f,-1,sizeof(f)); memset(used,false,sizeof(used));//枚举使用 共同的f数组 
    for (int i=0;i<=K;i++)//枚举：0-k，将上限转为定值 
	{
		
        int t=tdp(n,i);
        if (t==-1) {ans=-1; return;}
        ans=(ans+t)%mm;
    }
}
void print()
{
	printf("%d\n",ans);
}
int main()
{
	freopen("2017park.in","r",stdin); freopen("2017park.out","w",stdout);
    
    int T; scanf("%d",&T);
    while(T--)
	{
		init(); work(); print();
	}
    return 0;
}