#include <bits/stdc++.h>
using namespace std;

int n, m, ans, road_time[5005];
double E;

struct A_star
{
    int node;
    double now, f;

    inline bool operator<(const A_star &x) const
    {
        return x.f < f;
    }
};

struct Node
{
    int NO = 0;
    double v = 0x7fffffff;
    inline bool operator<(const Node &x) const
    {
        return x.v < v;
    }
};

Node node[5005];
vector< pair<int,double> > *adjacency_list = new vector< pair<int,double> >[5005];
vector< pair<int,double> > *not_adjacency_list = new vector< pair<int,double> >[5005];

inline void add(int start, int end, double value)
{
    adjacency_list[start].push_back(pair_{end, value});
    not_adjacency_list[end].push_back(pair_{start, value});
}

void dijkstra(int s)
{
    node[s].v = 0;
    vector<bool> vis(n + 5, false);
    priority_queue<Node> wait;
    wait.push(node[s]);
    while (!wait.empty())
    {
        Node tmp = wait.top();
        wait.pop();
        if (vis[tmp.NO])
            continue;
        vis[tmp.NO] = true;

        for (int next_node = 0; next_node < not_adjacency_list[tmp.NO].size(); next_node++)
        {
            if (node[not_adjacency_list[tmp.NO][next_node].first].v > (tmp.v + not_adjacency_list[tmp.NO][next_node].second))
            {
                node[not_adjacency_list[tmp.NO][next_node].first].v = (tmp.v + not_adjacency_list[tmp.NO][next_node].second);
                wait.push(node[not_adjacency_list[tmp.NO][next_node].first]);
            }
        }
    }
}

priority_queue<A_star> BFS;

void bfs(int start, int end)
{
    int end_time = E / node[start].v;
    A_star now, tmp;
    tmp.node = start,tmp.now=0,tmp.f=0;
    BFS.push(tmp);
    while (!BFS.empty())
    {
        now = BFS.top(), BFS.pop();
        if (now.f > E)
            return;
        road_time[now.node]++;
        if (now.node == end)
        {
            ans++, E -= now.f;
            continue;
        }

        if (road_time[now.node] > end_time)
            continue;
        for (int i = 0; i < adjacency_list[now.node].size(); i++)
        {
            tmp.node = adjacency_list[now.node][i].first,
            tmp.now = now.now + adjacency_list[now.node][i].second,
            tmp.f = tmp.now + node[now.node].v,
            BFS.push(tmp);
        }
    }
}

int main()
{
    cin >> n >> m >> E;
    for (int i = 0; i <= n; i++)
        node[i].NO = i;
    int a, b;
    double c;
    for (int i = 1; i <= m; i++)
        scanf("%d %d %lf", &a, &b, &c), add(a, b, c);
    dijkstra(n);
    bfs(1, n);
    cout << ans << endl;
    return 0;
}

初学k短路，同机房的同学也没看出来问题，望巨佬帮助