题解当打卡。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define PI  acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10,M = 4e5 + 10;
int mod = 1e9 +7;
int n,m,len,S,T;
int e[M],ne[M],w[M],h[N],hr[N],idx;
void add(int h[],int a,int b,int c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int dis[N];
bool vis[N];
struct node{
    int u,dis;
    bool operator<(const node &t)const{
        return dis > t.dis;
    }
};
void dijkstra(int h[]){
    priority_queue<node> q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[n] = 0;
    q.push({n,0});
    while(!q.empty()){
        node now = q.top();q.pop();
        int u = now.u;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = h[u] ; ~i ; i = ne[i]){
            int v = e[i];
            if(dis[v] > dis[u] + w[i]){
                dis[v] = dis[u] + w[i];
                q.push({v,dis[v]});
            }
        }
    }
}
bool find0;
bool st[N][55];
int f[N][55];
int dfs(int u,int k){
    if(st[u][k]){
        find0 = true;
        return 0;
    }
    if(find0) return 0;
    if(f[u][k] != -1) return f[u][k];
    f[u][k] = 0;
    st[u][k] = true;
    for(int i = h[u] ; ~i ; i = ne[i]){
        int v = e[i];
        //t为从u走到v剩余的需要多走的路程
        int t = k - (dis[v] + w[i] - dis[u]);
        if(t >= 0 && t <= len) f[u][k] = (f[u][k] + dfs(v,t)) % mod;
    }
    st[u][k] = false;
    if(u == n && k == 0) f[u][k] = 1;
    return f[u][k];
}
void solve(){
    cin >> n >> m >> len >> mod;
    memset(h,-1,sizeof(h));
    memset(hr,-1,sizeof(hr));
    idx = 0;
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        add(h,a,b,c),add(hr,b,a,c);
    }
    //在反图上跑最短路 
    dijkstra(hr);
    //记录是否有0环 
    find0 = false;
    int ans = 0;
    memset(f,-1,sizeof(f));
    for(int i = 0 ; i <= len ; ++i){
        ans = (ans + dfs(1,i)) % mod;
        if(find0){
            cout << -1 << endl;
            return;
        }
    } 
    cout << ans << endl;
}

signed main(){
    IOS;
    int tt;
    cin >> tt;
    while(tt--)
    solve();
    return 0;
}
/*
*
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/