// Slower C++ solution:
#include <bits/stdc++.h>

#define maxn 109

#define maxm 1009

using namespace std;

struct Edge

{

	int v,w,next;

}edge[maxm];

int n,m,tot,head[maxn];

int d[maxn][maxm],inq[maxn][maxm];

inline void addedge(int u,int v,int w)

{

	edge[tot].v=v;

	edge[tot].w=w;

	edge[tot].next=head[u];

	head[u]=tot++;

}

queue<pair<int,int> >Q;

void spfa()

{

	memset(d,0x3f,sizeof(d));

	d[1][0]=0;

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

	pair<int,int>tmp;

	while(!Q.empty())

	{

		tmp=Q.front();

		Q.pop();

		int x=tmp.first;

		int y=tmp.second;

		inq[x][y]=0;

		for(int e=head[x];e!=-1;e=edge[e].next)

		{

			int v=edge[e].v;

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

			{

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

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

				{

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

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

				}

			}

			if(d[v][y]>d[x][y]+edge[e].w)

			{

				d[v][y]=d[x][y]+edge[e].w;

				if(!inq[v][y])

				{

					inq[v][y]=1;

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

				}

			}

		}

	}

}

int main()

{

	int u,v,w,c;

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

	{

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

		tot=0;

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

		{

			scanf("%d%d%d",&u,&v,&w);

			addedge(u,v,w);

		}

		spfa();

		int ans=m;

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

		{

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

			{

				ans=i;

				break;

			}

		}

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

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3517730953585738x):
#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





*/