我输出的全是 -1，也不知道是为什么？？？

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define DEBUG printf("[YES]\n")
inline int read()
{   int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f; }
const int N = 1e6, M = 3e3;
int n, m, k, P;
int h[N], hs[N], e[N << 2], ne[N << 2], w[N << 2], idx;
int dist[N << 2]; bitset<N << 2> st; int f[M][M];
bool ins[N << 2][5];
inline void add(int a, int b, int c, int *h)
{   e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++ ; }
inline void SPFA()
{   st.reset();
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0; st[1] = true;
    queue<int> q; q.emplace(1);
    while (!q.empty())
    {   int t = q.front(); q.pop(); st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {   int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {   dist[j] = dist[t] + w[i];
                if (!st[j]) { q.emplace(j); st[j] = true; } } } } }
bool FU;
inline int DP(int u, int k)
{   if (k < 0)  return 0;
    if (ins[u][k]) { FU = true; return 0; }
    if (f[u][k]) return f[u][k];
    ins[u][k] = true;
    int ans = 0;
    for (int i = hs[u]; i != -1; i = ne[i])
    {
        int v = e[i], W = w[i];
        ans = (ans + DP(v, dist[u] - dist[v] + k - W)) % P;
        if (FU) return 0;
    }
    ins[u][k] = false;
    return f[u][k] = ans; }
signed main()
{
    freopen("P3953_5.in", "r", stdin);
    int T = read();
    while (T -- )
    {
        idx = 0; FU = false; 
        memset(f, NULL, sizeof(f));
        memset(ins, NULL, sizeof(ins));
        memset(h, EOF, sizeof(h)); 
        memset(hs, EOF, sizeof(h));
        n = read(), m = read(), k = read(), P = read();
        for (int i = 1; i <= m; i ++ )
        {   int u = read(), v = read(), val = read();
            add(u, v, val, h); add(v, u, val, hs); }
        SPFA(); DP(1, 0); f[1][0] = 1; 
        int ans = 0;
        for (int i = 0; i <= k; i ++ ) ans = (ans + DP(n, i) % P) % P;
        if (FU == true) { puts("-1");}
        else cout << ans % P << endl;
    }
    return 0;
}