RT。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pli = pair<ll, int>;

const int N = 1e5 + 5, K = 50 + 5;
const ll inf = 1e18;

int n, m;
ll k, mod;
ll dp[N][K]; // dp[i][j] : dis[1][i] == dis1[i] + k 的路径数量
vector<pair<int, ll>> G[N], rG[N]; // 原图，反图
vector<int> G0[N]; // 0边图
int in[N], ord[N], inx; // 入度，topo序
int id[N], pos[N];
ll dis1[N], disu[N], disn[N];
bool vis[N];

void dijkstra(int st, ll *dis, vector<pair<int, ll>> *G) {
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    fill(dis + 1, dis + 1 + n, inf);
    fill(vis + 1, vis + 1 + n, false);
    dis[st] = 0;
    pq.emplace(0, st);
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto e : G[u]) {
            int v = e.first;
            ll w = e.second;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.emplace(dis[v], v);
            }
        }
    }
}

void topo() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ord[u] = ++inx;
        for (int v : G0[u]) {
            if (--in[v] == 0) q.push(v);
        }
    }
}

void init() {
    memset(dp, 0, sizeof(dp));
    memset(in, -1, sizeof(in));
    inx = 0;
}

void clear(int n) {
    for (int i = 1; i <= n; i++) {
        G[i].clear();
        rG[i].clear();
        in[i] = -1;
        G0[i].clear();
    }
}

void Solve() {
    init();

    cin >> n >> m >> k >> mod;
    int u, v; ll w;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        rG[v].emplace_back(u, w); // 反图
    }

    // 最短路
    dijkstra(1, dis1, G); // 1 到 u
    dijkstra(n, disu, rG); // u 到 n
    dijkstra(n, disn, G); // n 到 u

    // 建0边图
    for (int u = 1; u <= n; u++) {
        for (auto e : G[u]) {
            int v = e.first;
            ll w = e.second;
            if (w == 0) {
                if (in[u] == -1) in[u] = 0;
                if (in[v] == -1) in[v] = 0;
                G0[u].push_back(v);
                in[v]++;
            }
        }
    }

    // 对0边图拓扑排序
    topo();

    // 两种无解的情况
    for (int i = 2; i < n; i++) {
        if (in[i] > 0 && dis1[i] + disu[i] <= dis1[n] + k) {
            cout << -1 << '\n';
            clear(n);
            return;
        }
    }
    if (dis1[n] == 0 && disn[1] == 0) {
        cout << -1 << '\n';
        clear(n);
        return;
    }

    // 排序
    iota(id + 1, id + 1 + n, 1);
    sort(id + 1, id + 1 + n, [&](int i, int j) { return dis1[i] == dis1[j] ? ord[i] < ord[j] : dis1[i] < dis1[j]; });
    for (int i = 1; i <= n; i++) {
        pos[id[i]] = i;
    }
    sort(dis1 + 1, dis1 + 1 + n);

    // 转移
    dp[1][0] = 1 % mod;
    for (int i = 0; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            int u = id[j];
            for (auto e : G[u]) {
                int v = e.first;
                ll w = e.second;
                if (dis1[pos[u]] + i + w - dis1[pos[v]] <= k && dis1[pos[u]] + i + w - dis1[pos[v]] >= 0) {
                    dp[v][dis1[pos[u]] + i + w - dis1[pos[v]]] += dp[u][i];
                    dp[v][dis1[pos[u]] + i + w - dis1[pos[v]]] %= mod;
                }
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i <= k; i++) ans = (ans + dp[n][i]) % mod;
    cout << ans << '\n';

    clear(n);
}

int main() {
    int T;
    cin >> T;
    while (T--) Solve();
    return 0;
}