#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
typedef long long ll;
template<typename T>
void read(T &num) {
    int ch = getchar();
    num = 0;

    while (ch < 48 || ch > 57)
        ch = getchar();

    while (ch >= 48 && ch <= 57)
        num = (num << 3) + (num << 1) + (ch ^ 48), ch = getchar();
}
const int maxn = 100005, maxm = 200005;
int T, n, m, k, p;
int head[maxn], total;
struct Edge {
    int to, next, len;
} e[maxm];
void add(int u, int v, int w) {
    e[++total] = Edge{v, head[u], w};
    head[u] = total;
}
void clear() {
    memset(head, 0, sizeof(int) * (n + 3));
    total = 0;
}
struct Input {
    int u, v, w;
} a[maxm];
bool vis[maxn];
ll dis_1[maxn], dis_n[maxn];
std::priority_queue<std::pair<ll, int>>q;
void dijkstra(int s, ll *dis) {
    memset(vis, 0, sizeof(bool) * (n + 3));
    memset(dis, 31, sizeof(ll) * (n + 3));
    dis[s] = 0;
    q.push({0, s});

    while (!q.empty()) {
        int u = q.top().second;
        q.pop();

        if (vis[u])
            continue;

        vis[u] = true;

        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;

            if (dis[v] > dis[u] + e[i].len) {
                dis[v] = dis[u] + e[i].len;
                q.push({-dis[v], v});
            }
        }
    }
}
int degree[maxn], id[maxn];
int queue[maxn], front, tail;
void toposort() {
    front = 1, tail = 0;
    queue[++tail] = 1;
    int now = 0;

    while (front <= tail) {
        int u = queue[front++];
        id[++now] = u;

        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;

            if ((--degree[v]) == 0)
                queue[++tail] = v;
        }
    }
}
int dp[maxn][51];
int solve() {
    read(n), read(m), read(k), read(p);
    clear();

    for (int i = 1; i <= m; i++) {
        read(a[i].u), read(a[i].v), read(a[i].w);
        add(a[i].u, a[i].v, a[i].w);
    }

    dijkstra(1, dis_1);
    clear();

    for (int i = 1; i <= m; i++)
        add(a[i].v, a[i].u, a[i].w);

    dijkstra(n, dis_n);
    clear();
    memset(degree, 0, sizeof(int) * (n + 3));
    memset(id, 0, sizeof(int) * (n + 3));

    for (int i = 1; i <= m; i++)
        if (dis_1[a[i].u] + a[i].w + dis_n[a[i].v] <= dis_1[n] + k && dis_1[a[i].u] + a[i].w == dis_1[a[i].v]) {
            add(a[i].u, a[i].v, 0);
            degree[a[i].v]++;
        }

    for (int i = 1; i <= m; i++)
        a[i].w = dis_1[a[i].u] + a[i].w - dis_1[a[i].v];

    toposort();

    for (int i = 1; i <= n; i++)
        if (degree[i])
            return -1;

    memset(dp, 0, sizeof(int) * 51 * (n + 3));
    dp[1][0] = 1;

    for (int j = 0; j <= k; j++) {
        for (int x = 1; x <= n; x++) {
            int u = id[x];

            for (int i = head[u]; i; i = e[i].next) {
                int v = e[i].to;
                dp[v][j] = (dp[v][j] + dp[u][j]) % p;
            }
        }

        for (int i = 1; i <= m; i++)
            if (a[i].w && j + a[i].w <= k)
                dp[a[i].v][j + a[i].w] = (dp[a[i].v][j + a[i].w] + dp[a[i].u][j]) % p;
    }

    ll answer = 0;

    for (int i = 0; i <= k; i++)
        answer += dp[n][i];

    return answer % p;
}
int main() {
    read(T);

    while (T--)
        printf("%d\n", solve());

    return 0;
}