#include <bits/stdc++.h>
using namespace std;
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 16;
struct CostGraph
{
    CostGraph(const int v) : edge(v) {}
    struct Edge
    {
        Edge(const int from, const int to, const int cost) : from{from}, to{to}, cost{cost} {}
        const int from, to, cost;
    };
    void addEdge(const int from, const int to, const int cost) { edge[from].push_back(Edge{from, to, cost}); }
    vector<vector<Edge>> edge;
};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (true) {
        int N, M, C;
        cin >> N >> M >> C;
        if (N == 0 and M == 0 and C == 0) { break; }
        CostGraph g(N);
        for (int i = 0; i < M; i++) {
            int f, t, c;
            cin >> f >> t >> c, g.addEdge(f - 1, t - 1, c);
        }
        vector<vector<int>> dp(N, vector<int>(N, INF<int>));
        using PP = pair<int, pair<int, int>>;
        priority_queue<PP, vector<PP>, greater<PP>> q;
        dp[0][0] = 0;
        q.push({0, {0, 0}});
        while (not q.empty()) {
            const auto& p = q.top();
            const int s = p.second.first, m = p.second.second, c = p.first;
            q.pop();
            if (dp[s][m] < c) { continue; }
            for (const auto& e : g.edge[s]) {
                if (dp[e.to][m] > dp[s][m] + e.cost) { dp[e.to][m] = dp[s][m] + e.cost, q.push({dp[e.to][m], {e.to, m}}); }
                if (m < N - 1 and dp[e.to][m + 1] > dp[s][m]) { dp[e.to][m + 1] = dp[s][m], q.push({dp[e.to][m + 1], {e.to, m + 1}}); }
            }
        }
        for (int i = 1; i < N; i++) {
            if (dp[N - 1][i] <= C) {
                cout << i << "\n";
                break;
            }
        }
    }
    return 0;
}

