#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define rg register
inline int read() {
    rg int x = 0, fh = 1;
    rg char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            fh = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * fh;
}
const int maxn = 1e5 + 5, maxk = 55;
int h[maxn], tot = 1;
struct asd {
    int to, nxt, val, op;
} b[maxn << 2];
void ad(int aa, int bb, int cc, int dd) {
    b[tot].to = bb;
    b[tot].nxt = h[aa];
    b[tot].val = cc;
    b[tot].op = dd;
    h[aa] = tot++;
}
int t, n, m, p, k, dis[maxn], ans, f[maxn][maxk];
bool vis[maxn], inq[maxn][maxk];
std::deque<int> q;
void spfa(int qd) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    q.push_back(1);
    dis[1] = 0;
    while (!q.empty()) {
        int now = q.front();
        q.pop_front();
        vis[now] = 0;
        for (int i = h[now]; i != -1; i = b[i].nxt) {
            if (!b[i].op)
                continue;
            rg int u = b[i].to;
            if (dis[u] > dis[now] + b[i].val) {
                dis[u] = dis[now] + b[i].val;
                if (!vis[u]) {
                    vis[u] = 1;
                    if (!q.empty() && dis[u] < dis[q.front()])
                        q.push_front(u);
                    else
                        q.push_back(u);
                }
            }
        }
    }
}
int dfs(int now, int val) {
    if (val > k || val < 0)
        return 0;
    if (inq[now][val]) {
        inq[now][val] = 0;
        return -1;
    }
    if (f[now][val] != -1)
        return f[now][val];
    inq[now][val] = 1;
    rg int nans = 0;
    for (rg int i = h[now]; i != -1; i = b[i].nxt) {
        rg int u = b[i].to;
        if (b[i].op)
            continue;
        rg int cs = dfs(u, val - b[i].val + dis[now] - dis[u]);
        if (cs == -1) {
            inq[cs][val] = 0;
            return -1;
        }
        nans = (nans + cs) % p;
    }
    if (now == 1 && val == 0)
        nans++;
    f[now][val] = nans;
    inq[now][val] = 0;
    return f[now][val];
}
int main() {
    t = read();
    while (t--) {
        memset(h, -1, sizeof(h));
        memset(b, 0, sizeof(b));
        memset(f, -1, sizeof(f));
        memset(inq, 0, sizeof(inq));
        tot = 1;
        ans = 0;
        n = read(), m = read(), k = read(), p = read();
        rg int aa, bb, cc;
        for (rg int i = 1; i <= m; i++) {
            aa = read(), bb = read(), cc = read();
            ad(aa, bb, cc, 1);
            ad(bb, aa, cc, 0);
        }
        spfa(1);
        bool jud = 0;
        for (rg int i = 0; i <= k; i++) {
            rg int now = dfs(n, i);
            if (now == -1) {
                jud = 1;
                break;
            }
            ans = (ans + now) % p;
        }
        if (jud) {
            printf("-1\n");
            continue;
        }
        printf("%d\n", ans);
    }
    return 0;
}

P3953 把第35行的queue开到外面就RE 开到函数里面就不会RE