#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
#include<ctime>
#define pb push_back
#define pii pair<int,int>
#define LL long long int
using namespace std;
const int MAXN=105;
const int MAXM=1005;
int n,m,C;
bool vis[MAXN][MAXM]={0};
int dp[MAXN][MAXM]; // dp[i][j]表示 从初始点到 i ?点修改 j 条??最小的花?
vector<pii >G[MAXN];
void spfa(int s){
    pii now;
    queue<pii >q; //（i?点，改j条?）
    dp[s][0]=0;
    q.push(make_pair(s,0));
    vis[s][0]=1;
    while(!q.empty()){
        int now_v=q.front().first,now_c=q.front().second;q.pop();
        if(now_c>m) continue; //修改?数大余了??数
        vis[now_v][now_c]=0;
        for(int i=0;i<G[now_v].size();++i){
            int next_v=G[now_v][i].first,w=G[now_v][i].second;

            if(dp[next_v][now_c+1]>dp[now_v][now_c]){ //修改?
                dp[next_v][now_c+1]=dp[now_v][now_c];
                if(!vis[next_v][now_c+1]) {
                    q.push(make_pair(next_v,now_c+1));
                    vis[next_v][now_c+1]=1;
                }
            }
            if(dp[now_v][now_c]+w<=C&&dp[next_v][now_c]>dp[now_v][now_c]+w){ //不修改?
                dp[next_v][now_c]=dp[now_v][now_c]+w;
                if(!vis[next_v][now_c]){
                    q.push(make_pair(next_v,now_c));
                    vis[next_v][now_c]=1;
                }
            }

        }
    }
    for(int i=0;i<=m;++i){
        if(dp[n][i]!=0xfffffff) {
            cout<<i<<endl;
            return;
        }
    }
}
int main(){
    int a,b,c;
    while(scanf("%d%d%d",&n,&m,&C)!=EOF){
        memset(vis,0,sizeof(vis));
        for(int i=0;i<MAXN;++i) for(int j=0;j<MAXM;++j) dp[i][j]=0xfffffff;
        for(int i=0;i<=n;++i) G[i].clear();
        for(int i=0;i<m;++i){
            scanf("%d%d%d",&a,&b,&c);
            G[a].pb(make_pair(b,c));
        }
        spfa(1);
    }
}