// This code is AI-generated. (AI 生成的代码)
// NOIP2017 逛公园: one Dijkstra from n on the reversed graph gives dist(u->n).
// Then memoized DFS from 1 with remaining budget: the extra cost of edge u->v is
// w - (dist[u]-dist[v]). Revisiting a state on the current DFS stack means a
// zero-extra cycle => infinitely many routes (-1).
#include <cstdio>
#include <cstring>
#include <utility>
using namespace std;
typedef pair<int,int> P;
enum { MAXN = 100005, MAXE = 400005, MAXK = 55 };
static int hf[MAXN], nf[MAXE], tf[MAXE], wf[MAXE], fc;
static int hr[MAXN], nr[MAXE], tr[MAXE], wr[MAXE], rc;
static int d[MAXN];
static int dp[55][MAXN];
static char done[55][MAXN], onstk[55][MAXN];
static int n, K, mod;
static char buf[1 << 25];
static char ob[1 << 22];
static char *op;
static P heap[MAXE];
static int hn;
static inline void hpush(P x) {
int i = hn++;
heap[i] = x;
while (i) {
int p = (i - 1) >> 1;
if (heap[p].first <= heap[i].first) break;
P t = heap[p]; heap[p] = heap[i]; heap[i] = t;
i = p;
}
}
static inline P hpop() {
P r = heap[0];
heap[0] = heap[--hn];
int i = 0;
for (;;) {
int l = 2 * i + 1, rr = l + 1, m = i;
if (l < hn && heap[l].first < heap[m].first) m = l;
if (rr < hn && heap[rr].first < heap[m].first) m = rr;
if (m == i) break;
P t = heap[m]; heap[m] = heap[i]; heap[i] = t;
i = m;
}
return r;
}
static void dij() {
const int INF = 0x3f3f3f3f;
for (int i = 1; i <= n; i++) d[i] = INF;
hn = 0; d[n] = 0; hpush(P(0, n));
while (hn) {
P x = hpop();
int u = x.second;
if (x.first > d[u]) continue;
for (int e = hr[u]; e; e = nr[e]) {
int v = tr[e], nd = x.first + wr[e];
if (nd < d[v]) { d[v] = nd; hpush(P(nd, v)); }
}
}
}
static int dfs(int u, int rem) {
if (onstk[rem][u]) return -1;
if (done[rem][u]) return dp[rem][u];
onstk[rem][u] = done[rem][u] = 1;
long long val = (u == n);
for (int e = hf[u]; e; e = nf[e]) {
int v = tf[e];
int extra = wf[e] - (d[u] - d[v]);
if (extra > rem) continue;
int r = dfs(v, rem - extra);
if (r < 0) { dp[rem][u] = -1; return -1; }
val += r;
if (val >= mod) val -= mod;
}
onstk[rem][u] = 0;
dp[rem][u] = (int)val;
return (int)val;
}
static const char *gp;
static inline int qr() {
while (*gp && (*gp < '0' || *gp > '9')) gp++;
int v = 0;
while (*gp >= '0' && *gp <= '9') v = v * 10 + (*gp++ - '0');
return v;
}
int main() {
int len = (int)fread(buf, 1, sizeof(buf) - 1, stdin);
buf[len] = 0;
gp = buf; op = ob;
int T = qr();
while (T--) {
n = qr(); int m = qr(); K = qr(); mod = qr();
fc = 1; rc = 1;
for (int i = 0; i <= n; i++) { hf[i] = 0; hr[i] = 0; }
for (int i = 0; i < m; i++) {
int u = qr(), v = qr(), w = qr();
tf[fc] = v; wf[fc] = w; nf[fc] = hf[u]; hf[u] = fc++;
tr[rc] = u; wr[rc] = w; nr[rc] = hr[v]; hr[v] = rc++;
}
dij();
for (int j = 0; j <= K; j++)
memset(done[j], 0, n + 1), memset(onstk[j], 0, n + 1);
int ans = dfs(1, K);
if (ans < 0) { *op++ = '-'; *op++ = '1'; *op++ = '\n'; }
else {
char t[16]; int kk = 0;
if (!ans) t[kk++] = '0';
while (ans) { t[kk++] = (char)('0' + ans % 10); ans /= 10; }
while (kk) *op++ = t[--kk];
*op++ = '\n';
}
}
fwrite(ob, 1, op - ob, stdout);
return 0;
}