// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;

struct Edge {int v, w;};
vector<Edge> G1[MAXN], G2[MAXN];

int T, N, M, K, P;
bool fail;
int f[MAXN][51];
int d[MAXN];
bool vis[MAXN];
bool ins[MAXN][51];

void Dijkstra() {
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    priority_queue<pair<int, int> > q;
    q.push(make_pair(0, 1));
    d[1] = 0;
    while (q.size()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (vector<Edge>::iterator it = G1[u].begin(); it != G1[u].end(); it++) {
            int v = it->v, w = it->w;
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                q.push(make_pair(-d[v], v));
            }
        }
    }
}

inline int dp(int u, int k) {
    if (k < 0) return 0;
    if (ins[u][k]){
        fail = 1;
        return 0;
    }
    if (f[u][k]) return f[u][k];
    ins[u][k] = 1;
    int ans = 0;
    for (vector<Edge>::iterator it = G2[u].begin(); it != G2[u].end(); it++) {
        int p = it->v, w = it->w;
        ans = (ans + dp(p, d[u] - d[p] + k - w))%P;
        if (fail == 1) return 0;
    }
    ins[u][k] = 0;
    return f[u][k] = ans;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d%d", &N, &M, &K, &P);
        for (register int i = 1; i <= M; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            G1[u].push_back((Edge){v, w});
            G2[v].push_back((Edge){u, w});
        }
        Dijkstra();
        dp(1, 0);
        f[1][0] = 1;
        int ans = 0;
        for (register int i = 0; i <= K; ++i) {
            ans = (ans + dp(N, i))%P;
        }
        if(fail == 1) puts("-1");
        else printf("%d\n", ans);
        fail = 0;
        memset(f, 0, sizeof(f));
        memset(ins, 0, sizeof(ins));
        for (register int i = 1; i <= N; ++i) {
            G1[i].clear(), G2[i].clear();
        }
    }
}

这篇题解不初始化先跑一遍dp是为什么呢？