关于标题：本人不会链前所以猜测是邻接表，但是用swap大法也MLE了所以可能是别的问题，但是找不出来了

//
//  Created by mori
//
//  Coded with Visual Studio Code
//

#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
typedef vector <int> vci;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;

#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)
#define cat const auto &
#define at auto &

template <typename T>
void ckmin (T &_0, T _1) { if (_1 < _0) _0 = _1; }

template <typename T>
void ckmax (T &_0, T _1) { if (_1 > _0) _0 = _1; }

int read () {
    int res = 0;
    bool f = false;
    char temp = getchar();
    for (; !isdigit(temp); temp = getchar()) f = temp == '-';
    for (; isdigit(temp); temp = getchar()) res = res * 10 + temp - '0';
    if (f) return -res;
    return res;
}

char gc () {
    char temp = getchar();
    while (temp == '\n' || temp == '\r' || temp == ' ') temp = getchar();
    return temp;
}

struct MODER {
    ll p, m;
    explicit MODER (ll tmp) : p (tmp), m (((lll)1 << 63) / p) {}
    ll operator () (ll x) {
        ll q = ((lll) x * m) >> 63;
        x -= p * q;
        if (x >= p) return x - p;
        return x;
    }
};

const string myfile = "iakioi";
void file () {
    string in = myfile + ".in", out = myfile + ".out";
    freopen(in.c_str(), "r", stdin); freopen(out.c_str(), "w", stdout);
}

constexpr int maxn = 1e5 + 5, inf = 1e9;
int n, m, k, p, dis[maxn], f[maxn][55];
MODER mod(12345);

struct EDGE {
    int v, w;
    operator int () const { return v; }
    EDGE (int vv, int ww) : v(vv), w(ww) {} 
};
vector <EDGE> e[maxn], e2[maxn];

void dist () {
    rep (i, 1, n - 1) dis[i] = inf;
    dis[n] = 0;
    priority_queue <pii> q; q.emplace(0, n);
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        for (cat v : e[u])
            if (dis[v] > dis[u] + v.w)
                dis[v] = dis[u] + v.w, q.emplace(-dis[v], v);
    }
}

bool vis[maxn][55], noa;
int dfs (int u, int x) {
    if (x < 0 || x > k) return 0;
    if (f[u][x]) return f[u][x];
    if (vis[u][x]) { printf("-1\n"); noa = true; }
    vis[u][x] = true;
    if (u == n && x == 0) ++f[u][x];
    for (cat v : e2[u]) f[u][x] = mod((ll) f[u][x] + dfs(v, x - (dis[v] + v.w - dis[u])));
    vis[u][x] = false; return f[u][x];
}

signed main () {
    int T = read();
    while (T--) {
        n = read(), m = read(), k = read(), p = read(), mod = MODER(p);
        rep (i, 1, n) vector <EDGE> ().swap(e[i]), vector <EDGE> ().swap(e2[i]);
        rep (i, 1, m) {
            int u = read(), v = read(), w = read();
            e[v].emplace_back(u, w); e2[u].emplace_back(v, w);
        }
        memset(f, 0, sizeof f); noa = false;
        dist(); memset(vis, 0, sizeof vis); int ans = 0;
        rep (i, 0, k) ans = mod((ll) ans + dfs(1, i));
        if (!noa) printf("%d\n", ans);
    }
    return 0;
}