#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,P> PP;
const long long int MOD = 1000000007;
const int INF = 1000000000;

int n, m, c;
int dp[101*100];
vector<P> e[101*100];
int debug;

void solve(){
    rep(i,101*100) e[i].clear();
    rep(i,m){
        int f, t, x;
        cin >> f >> t >> x;
        f--; t--;
        for(int j = 0; j < n; j++){
            e[j*n+f].push_back(P(j*n+t,x));
        }
        for(int j = 0; j < n-1; j++){
            e[j*n+f].push_back(P((j+1)*n+t,0));
        }
    }
    rep(i,101*100) dp[i] = INF;
    priority_queue<P,vector<P>, greater<P> > que;
    que.push(P(0,0));
    dp[0] = 0;
    while(!que.empty()){
        P p = que.top();
        que.pop();
        if(p.first > dp[p.second]) continue;
        rep(i,e[p.second].size()){
            P to = e[p.second][i];
            if(dp[to.first] > dp[p.second]+to.second && dp[p.second]+to.second <= c){
                dp[to.first] = dp[p.second]+to.second;
                que.push(P(dp[to.first],to.first));
            }
        }
    }
    for(int i = 0; i <= n; i++){
        if(dp[i*n+n-1] != INF){
            cout << i << endl;
            return;
        }
    }
}

int main(){
    while(cin >> n >> m >> c){
        debug++;
        if(n == 0 && m == 0 && c == 0) break;
        solve();
    }
}