// 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.4701383122249736x):
#include<cstdio>

#include<vector>

#include<iostream>

#include<map>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cmath>

#define eps 1e-10

#define inf 100000000

using namespace std;

int n,m,c;

struct node

{

    int t,cost;

    node(int t=0,int cost=0):t(t),cost(cost) {}

};

vector<node> G[105];

int d[105][105];

void spfa()

{

    queue<pair<int,int> > q;

    bool vis[105][105];

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

    for(int j=0;j<=n;j++) d[i][j]=inf;

    d[1][0]=0;memset(vis,0,sizeof(vis));

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

    while(!q.empty())

    {

        pair<int,int> p=q.front();q.pop();

        int x=p.first,y=p.second;

        vis[x][y]=0;

        for(int i=0;i<G[x].size();i++)

        {

            int v=G[x][i].t,co=G[x][i].cost;

            if(d[v][y]>d[x][y]+co)

            {

                d[v][y]=d[x][y]+co;

                if(!vis[v][y])

                {

                    vis[v][y]=1;

                    q.push(make_pair(v,y));

                }

            }

            if(y<n&&d[v][y+1]>d[x][y])

            {

                d[v][y+1]=d[x][y];

                if(!vis[v][y+1])

                {

                    vis[v][y+1]=1;

                    q.push(make_pair(v,y+1));

                }

            }

        }



    }

}

main()

{

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

    {

        memset(G,0,sizeof(G));

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

        {

            int s,t,c;

            scanf("%d%d%d",&s,&t,&c);

            G[s].push_back(node(t,c));

        }

        spfa();

        int ans;

        for(int j=1;j<=n;j++)

        if(d[n][j]<=c) {ans=j;break;}

        cout<<ans<<endl;

    }

}