// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <string.h>

#include <vector>

#include <cmath>

#include <queue>

#include <map>

using namespace std;

const int maxm = 1000*4;

const int maxn = 105;

const int inf = 100000000;

int n,m,c;

int dp[maxn][maxm];

bool vis[maxn][maxm];

struct node

{

    int to;

    int next;

    int w;

}edge[maxm];

int head[maxn];

int top;

void bfs()

{



    queue<pair <int,int> > Q;

    for(int i=0;i<=n;i++)

    for(int j=0;j<=m;j++)

    {

        dp[i][j]=inf;

    }

    vis[1][0]=1;

    dp[1][0]=0;

    Q.push(make_pair(1,0));

    while(!Q.empty())

    {



        int now = Q.front().first;

        int tim = Q.front().second;

        Q.pop();

        vis[now][tim]=0;

        for(int k=head[now];k!=-1;k=edge[k].next)

        {

            int to = edge[k].to;

            if(dp[now][tim] +edge[k].w < dp[to][tim])

            {

                  dp[to][tim] = dp[now][tim]+edge[k].w;

                  if (!vis[to][tim])

                    {

                        Q.push(make_pair(to,tim));

                        vis[to][tim] = 1 ;

                    }

            }

            if (dp[now][tim] < dp[to][tim+1])

            {

                dp[to][tim+1] = dp[now][tim];

                if (!vis[to][tim+1])

                {

                    Q.push(make_pair(to,tim+1));

                    vis[to][tim+1]= 1 ;

                }

            }

        }

    }

}

void init()

{

    top=0;

    memset(head,-1,sizeof(head));

    memset(vis,false,sizeof(vis));

}

void add(int from,int to,int w)

{

    edge[top].to=to;

    edge[top].w=w;

    edge[top].next = head[from];

    head[from]  =top++;

}

int main()

{

    while(scanf("%d%d%d",&n,&m,&c),n+m+c)

    {

        init();

        for(int i=1;i<=m;i++)

        {

            int a,b,c;

            scanf("%d%d%d",&a,&b,&c);

            add(a,b,c);

        }

        bfs();

        //cout<<"here"<<endl;

        for(int i=0;i<=n;i++)

        if(dp[n][i] <= c)

        {

            printf("%d\n",i);

            break;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.337747529388624x):
#include<bits/stdc++.h>

using namespace std;

const int MAXN=105;

const int INF=0x3f3f3f3f;

bool vis[MAXN];

int a[MAXN][MAXN], dp[MAXN][MAXN];

queue<int> Q;

void spfa(int s,int n){

    memset(vis,0,sizeof vis);

    while(!Q.empty()) Q.pop();

    Q.push(s);

    dp[1][0]=0;

    vis[s]=true;

    while(!Q.empty()){

        int u=Q.front(); Q.pop();

        vis[u]=false;

        for(int i=1; i<=n; i++){

            if(a[u][i]!=-1){

                for(int j=0; j<=n; j++){

                    if(dp[u][j]+a[u][i]<dp[i][j]){

                        dp[i][j]=dp[u][j]+a[u][i];

                        if(!vis[i]){

                            Q.push(i); vis[i]=true;

                        }

                    }

                    if(j&&dp[i][j]>dp[u][j-1]){

                        dp[i][j]=dp[u][j-1];

                        if(!vis[i]){

                            Q.push(i); vis[i]=true;

                        }

                    }

                }

            }

        }

    }

}

int main(){

    int n, m, c, x, y, w;

    while(cin>>n>>m>>c&&n){

        memset(a,-1,sizeof a);

        memset(dp,0x3f,sizeof dp);

        for(int i=0; i<m; i++){

            cin>>x>>y>>w;

            a[x][y]=w;

        }

        spfa(1,n);

        for(int i=0; i<=n; i++){

            if(dp[n][i]<=c){

                printf("%d\n",i);

                goto next;

            }

        }

        next:;

    }

    return 0;

}