本题要求求路径数，图论的最短路算法可求不了路径数，那么可以想到在图里面使用动态规划的方式去求路径数。
在本题里面可以得出从某一点到下一点的路径方式有多少取决去这一点之前的路径数，以及该点和下一点的路径数。
那么就可以知道之间可以使用动态规划去求解。
但本题有要求路径长度不能超过n+k，所以dp数组为：dp[i][j]，其中i代表节点编号，j代表还剩余了多少多余的路径长度。
状态转移方程：dp[number][remain] = (dp[number][remain]%p + dp[next][remain-duo]%p)%p;
而想要知道在某段路里面多走了多少路径长度，就需要知道这条路两端节点到n的最短距离是多少。拿最短距离相减就是这两个节点之间的最短路径长度。
那么就可以得到多走了多少。
由于要求所有节点到n的最短路径，所以需要建立一个反向图，然后使用Dijkstra去求解。
对于本图来说正常动态规划要考虑的动态太多，所以直接使用记忆化搜索去做。
对于如果有无穷多条合法的路线来说：这种情况只有出现0环的时候。那么0环的特点是走一圈后路径长度没有消耗。所以如果在记忆化搜素的时候重复的搜到了某个状态
那么就是出现了0环（要在同一个递归过程中搜到）。 
#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
const int maxn = 100000+10;
const int maxm = 200000+10;
struct sy{
    int next;
    int to;
    int w;
} edge[maxm], edge2[maxm];
int head[maxm];
int cnt;
int head2[maxm];
int cnt2;
int n, m, k, p;
struct Node{
    int number;
    int val;
    bool operator < (const Node& n) const
    {
        return val>n.val;
    }
} node[maxm];
priority_queue<Node> pq;
int dist[maxm];
bool vis[maxm];
bool flag[maxm][55];
int dp[maxm][55];

void add_edge(int x, int y, int w)
{
    edge[++cnt].next = head[x];
    edge[cnt].to = y;
    edge[cnt].w = w;
    head[x] = cnt;
}

void add_edge2(int x, int y, int w)
{
    edge2[++cnt2].next = head2[x];
    edge2[cnt2].to = y;
    edge2[cnt2].w = w;
    head2[x] = cnt2;
}

void init()
{
    memset(edge, 0, sizeof(edge));
    memset(edge2, 0, sizeof edge2);
    memset(head, -1, sizeof head);
    memset(head2, -1, sizeof head2);
    cnt = 0;cnt2 = 0;
    memset(node, 0, sizeof node);
    while (pq.size()) pq.pop();
    memset(dist, 0, sizeof dist);
    memset(vis, 0, sizeof vis);
    memset(flag, 0, sizeof flag);
    memset(dp, 0, sizeof dp);
}

void Dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    pq.push({n, 0});
    dist[n] = 0;
    while (pq.size())
    {
        int number = pq.top().number;
        pq.pop();
        if (vis[number]) continue;
        vis[number] = true;
        for (int i=head[number];~i;i=edge[i].next)
        {
//             cout<<"i="<<i<<endl;
            int next = edge[i].to;
            int w = edge[i].w;
            if (dist[number]+w<dist[next])
            {
                dist[next] = dist[number]+w;
                pq.push({next, dist[next]});
            }
        }
    }
}
//记忆化搜索，dp[i][j],i代表节点编号，j代表剩余的K值。
//dp[i][j] = dp[I][j-这条路消耗多少K值];
int Memorized_search(int number, int remain)
{
//     cout<<"number="<<number<<endl;
//     cout<<"remain="<<remain<<endl;
    if (flag[number][remain]) return dp[number][remain] = -1;
    if (dp[number][remain]) return dp[number][remain];
    if (number==n) dp[number][remain] = 1;
    else dp[number][remain] = 0;
    flag[number][remain] = true;
    for (int i=head2[number];~i;i=edge2[i].next)
    {
//         cout<<"number="<<number<<endl;
//         cout<<"i="<<i<<endl;
        int next = edge2[i].to;
        int w = edge2[i].w;
//         cout<<"dist[number]="<<dist[number]<<" dist[next]="<<dist[next]<<endl;
        int duo = w-(dist[number]-dist[next]);
//         cout<<"duo="<<duo<<endl;
        if (duo<=remain)
        {
            int pi = Memorized_search(next, remain-duo);
            if (pi==-1)
                return dp[number][remain] = -1;
            dp[number][remain] = (dp[number][remain]%p + pi%p)%p;
        }
    }
    flag[number][remain] = false;
    return dp[number][remain];
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    int a, b, c;
    int T;
    cin>>T;
    while (T--)
    {
        init();
        cin>>n>>m>>k>>p;
        for (int i=1;i<=m;i++)
        {
            cin>>a>>b>>c;
            add_edge(b, a, c);
            //建立反图，用于记忆化搜索。
            add_edge2(a, b, c);
        }
        //找出1到其他点的最短路。
        Dijkstra();
//         for (int i=1;i<=n;i++)
//         {
//             cout<<dist[i]<<' ';
//         }
//         cout<<endl;
        cout<<Memorized_search(1, k)<<endl;
    }
    
    
    return 0;
}