#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 4e5 + 10, K = 55;

int n, m, k, P;
int h[N], e[M], w[M], ne[M], idx;

int dist[N];
int in_stk[N][K], inf;
int f[N][K];
void add(int a, int b, int c)
{
    e[idx] = b; w[idx] = c;
    ne[idx] = h[a]; h[a] = idx ++;
}

bool st[N];

void dij()
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);

    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.y;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; ~i; i = ne[i])
        {
            if(i & 1) continue; // 反向边不要
            int j = e[i];
            if(dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int dp(int b, int y)
{
    if(in_stk[b][y])
    {
        inf = true;
        return 0;
    }

    int &v = f[b][y];
    if(v != -1) return v;

    in_stk[b][y] = true;

    v = 0;
    if(b == 1 && !y) v++;

    for(int i = h[b]; ~i; i = ne[i])
    {
        if(!(i & 1)) continue;
        int a = e[i];
        int x = dist[b] + y - w[i] - dist[a];
        if(x < 0 || x > k) continue;
        v = (v + dp(a, x)) % P;
        if(inf) return 0;
    }
    in_stk[b][y] = false;
    return v;
}

int main()
{   
    int T;
    cin >> T;
    while(T --)
    {
        cin >> n >> m >> k >> P;
        memset(h, -1, sizeof h);
        idx = 0;
        while(m --)
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c), add(b,a , c);
        }
        dij();
        memset(f, -1, sizeof f);
        memset(in_stk, 0, sizeof in_stk);
        inf = false;

        int res = 0;
        for(int i  = 0; i <= k; i++)
        {
            res = (res + dp(n, i)) % P;
            if(inf) break;
        }

        if(inf) res = -1;
        cout << res << endl;
    }
    return 0;
}

/*
f(b, y)来表示从起点走到b，且路径长度恰好是y的所有路线的数量。
f(b, y) = f(a1, y-w1) + f(a2, y-w2) + ...

起点到终点最短路径为d[n], 那么f(b, y) 中y的取值范围应该是d[n] ~ d[n] + k;

请问普通点， 比如点b 是否也能满足f(b, d[b]), f(b, d[b] + k)

对于每个点b来说，只需要考虑满足d[b] <= y <= d(b) + k的y，这种y只有k+1
f(b, y) 表示从起点走到点b且长度恰好为d(b) + y的所有路线的数量

对于b的每个临点： x = db + y - wk - da
无穷多解： 某个点存在权值为0的环，且能到n，且起点能到这个点
即记忆化搜索时有循环依赖
*/