#include<bits/stdc++.h>
#define N 100007
#define M 57
using namespace std;
vector<int> vec[N];
vector<int> w[N];
vector<int> rev[N];
vector<int> revc[N];
int n, m, k, p;
int vis[N], dis[N], f[N][M], book[N][M], flag;
void spfa(int s)
{
	deque<int> que(0);
	que.push_back(s);
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	while(!que.empty())
	{
		int u = que.front();
		que.pop_front();
		for(int i = 0; i < rev[u].size(); i++)
		{
			int v = rev[u][i];
			if(dis[u]+revc[u][i]<dis[v])
			{
				dis[v] = dis[u]+revc[u][i];
				if(!vis[v])
				{
					que.push_back(v);
					vis[v] = 1;
				}
			}
		}
		vis[u] = 0;
	}
	return;
}
int dfs(int x, int k)
{
    if(f[x][k]>=0)
    {
        return f[x][k];
    }
    f[x][k] = 0;
    book[x][k] = 1;
    for(int i = 0; i < vec[x].size(); i++)
    {
        int y = vec[x][i], c = w[x][i];
        int t = k-c+dis[x]-dis[y];
        if(t<0||t>k)
        {
            continue;
        }
        if(book[y][t])
        {
            flag = 1;
            return 0;
        }
        f[x][k] += dfs(y, t);
        f[x][k] %= p;
    }
    book[x][k] = 0;
    return f[x][k];
}
int main()
{
	int t;
	freopen("2017park.in", "r", stdin);
	freopen("2017park.out", "w", stdout);
	scanf("%d", &t);
	while(t--)
	{
	    int ans = 0;
		scanf("%d%d%d%d", &n, &m, &k, &p);
		for(int i = 1; i <= n; i++)
		{
			vec[i].clear();
			w[i].clear();
			rev[i].clear();
			revc[i].clear();
		}
		for(int i = 1; i <= m; i++)
		{
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			vec[x].push_back(y);
			w[x].push_back(z);
			rev[y].push_back(x);
			revc[y].push_back(z);
		}
		spfa(n);
		memset(f, -1, sizeof(f));
		memset(book, 0, sizeof(book));
		flag = 0;
		f[n][0] = 1;
		for(int i = 0; i <= k; i++)
        {
            ans += dfs(1, i);
            ans %= p;
        }
        if(flag)
        {
            puts("-1");
            continue;
        }
		printf("%d\n", ans);
	}
	return 0;
}