#include <bits/stdc++.h>
using namespace std;
typedef pair<int, double> pid;
typedef pair<double, int> pdi;
const double INF = 1e18;
int N, M,cnt[5005];
vector<pid> adj[5005], rev_adj[5005];
double dist[5005],E;
void dijkstra(int start) {
    priority_queue<pdi, vector<pdi>, greater<pdi>> pq;
    fill(dist, dist + N + 1, INF);
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        double d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (d > dist[u]) continue;
        for (auto &edge : rev_adj[u]) {
            int v = edge.first;
            double w = edge.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}
int astar() {
    priority_queue<pdi, vector<pdi>, greater<pdi>> pq;
    pq.push({dist[1], 1});
    int ans = 0;
    double total = 0;
    while (!pq.empty()) {
        double cost = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (u == N) {
            if (total + (cost - dist[N]) > E + 1e-8) {
                break;
            }
            total += cost - dist[N];
            ans++;
            if (total >= E - 1e-8) {
                break;
            }
            continue;
        }
        if (cnt[u]++ > E) continue;
        for (auto &edge : adj[u]) {
            int v = edge.first;
            double w = edge.second;
            pq.push({cost - dist[u] + w + dist[v], v});
        }
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> E;
    for (int i = 0; i < M; ++i) {
        int s, t;
        double e;
        cin >> s >> t >> e;
        adj[s].emplace_back(t, e);
        rev_adj[t].emplace_back(s, e);
    }
    dijkstra(N);
    cout << astar() << endl;
    return 0;
}