#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 400010, S = 51;
typedef pair<int, int> PII;
int T;
int n, m, K, P;
int ans;
int h[N], f[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N][S];
bool st[N], vis[N][S], flag = false;
void init()
{
flag = false;
idx = 0, ans = 0;
memset(f, -1, sizeof f);
memset(h, -1, sizeof h);
memset(cnt, -1, sizeof cnt);
memset(st, false, sizeof st);
}
void add(int h[], int a, int b, int c)
{
w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dijkstra() // 反向 Dijkstra, 便于后面算冗余
{
priority_queue<PII, vector<PII>, greater<PII> > heap;
memset(dist, 0x3f, sizeof dist);
dist[n] = 0;
heap.push({0, n});
while (heap.size())
{
PII t = heap.top();
heap.pop();
int ver = t.second;
if (st[ver]) continue;
st[ver] = true;
for (int i = f[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
}
// 从 u 走到 n, 消耗了 s 个冗余单位的方案数
int dfs(int u, int s)
{
// 搜索的过程中,如果一个点两次进入我们的最短路,那么显然就是 0 环.
if (vis[u][s]) // 重复搜到了这个点且冗余未发生变化
{
flag = true; // 也就是出现了 0 环
return 0;
}
if (cnt[u][s] != -1) return cnt[u][s]; // 记忆化搜索,
vis[u][s] = true;
int &Cnt = cnt[u][s] = 0; // 方案数
for (int i = h[u]; i != -1; i = ne[i])
if (!flag) { // 没有发现零环的话
int v = e[i];
// min(n -> v) + u -> v - min(n -> u) = u -> v 的冗余
// u -> n 原冗余 - u -> v 的冗余 = v -> n 的冗余
int k = s - (dist[v] + w[i] - dist[u]);
if (0 <= k && k <= K) Cnt = (Cnt + dfs(v, k)) % P; // 计算方案数
}
if (flag) return 0;
vis[u][s] = false;
if (u == n && s == 0) Cnt = 1;
return Cnt;
}
int main()
{
scanf("%d", &T);
while (T -- )
{
init();
scanf("%d %d %d %d", &n, &m, &K, &P);
while (m -- )
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
add(h, a, b, c), add(f, b, a, c);
}
dijkstra();
for (int i = 0; i <= K; i ++ ) // 计算每一类冗余产生的方案数
if (!flag) // 没有 0 环
{
memset(vis, false, sizeof vis); // 初始化
ans = (ans + dfs(1, i)) % P; // 累计
}
if (flag) ans = -1; // 方案无数
printf("%d\n", ans);
}
return 0;
}