// 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.3250845452687643x):
#include <stdio.h>    

#include <string.h>    

#include <set>  

#include <map>  

#include <algorithm>  

#include <iostream>  

#include <vector>  

#include <string>  

#include <queue>

#include <cmath>  

template <class T>

inline bool rd(T &ret) {

	char c; int sgn;

	if (c = getchar(), c == EOF) return 0;

	while (c != '-' && (c<'0' || c>'9')) c = getchar();

	sgn = (c == '-') ? -1 : 1;

	ret = (c == '-') ? 0 : (c - '0');

	while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');

	ret *= sgn;

	return 1;

}

template <class T>

inline void pt(T x) {

	if (x <0) {

		putchar('-');

		x = -x;

	}

	if (x>9) pt(x / 10);

	putchar(x % 10 + '0');

}

using namespace std;

const int inf = 1e8;

const int N = 105;

const int M = 100010;

struct Edge{

	int from, to, dis, nex;

}edge[1005];

int head[N], edgenum;

void add(int u, int v, int dis){

	Edge E = { u, v, dis, head[u] };

	edge[edgenum] = E;

	head[u] = edgenum++;

}

void init(){ memset(head, -1, sizeof head); edgenum = 0; }

int n, m, c;

int dp[N][M], vis[N];

void bfs(){

	queue<int>q;

	q.push(n);

	dp[n][0] = 0;

	while (!q.empty()){

		int u = q.front(); q.pop(); vis[u] = 0;

		for (int i = head[u]; ~i; i = edge[i].nex){

			int v = edge[i].to;

			bool ok = false;

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

			{

				if (dp[u][j] == inf)continue;

				if (dp[v][j] > dp[u][j] + 1)

				{

					dp[v][j] = dp[u][j] + 1; ok = true;

				}

				if (j + edge[i].dis <= c && dp[v][j + edge[i].dis] > dp[u][j])

				{

					dp[v][j + edge[i].dis] = dp[u][j]; ok = true;

				}

			}

			if (ok && vis[v] == 0)vis[v] = 1, q.push(v);

		}

	}

}

int main(){

	int u, v, d;

	while (cin>>n>>m>>c, n+m+c){

		init();

		memset(vis, 0, sizeof vis);

		for (int i = 1; i <= n; i++)for (int j = 0; j <= c; j++)dp[i][j] = inf;

		while (m--)

		{

			rd(u); rd(v); rd(d);

			add(v, u, d);

		}

		bfs();

		int ans = inf;

		for (int i = 0; i <= c; i++)ans = min(ans, dp[1][i]);

		pt(ans); puts("");

	}

	return 0;

}

/*

3 3 3

1 2 10

1 2 5

2 3 3



4 5 3

1 2 10

1 2 5

2 3 3

3 4 1

4 2 6



4 5 1

1 2 10

1 2 5

2 3 3

3 4 1

4 2 6





4 5 8

1 2 10

1 2 5

2 3 3

3 4 1

4 2 6



4 5 0

1 2 10

1 2 5

2 3 3

3 4 1

4 2 6





*/