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

#include <cstring>

#include <queue>

#include <utility>

using std::queue;

using std::pair;

using std::make_pair;



const int N = 100 + 10;

const int M = 1000 + 10;



int cap[N][N], n, m, C;

int dis[N][M];

bool vis[N][M];

typedef pair<int, int> pir;

queue<pir> Q;



int solve()

{

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

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

	memset(vis, 0, sizeof(vis));

	vis[1][0] = 1; dis[1][0] = 0;

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

	while(!Q.empty())

	{

		pir tmp = Q.front(); Q.pop();

		int i = tmp.first, k = tmp.second;

		vis[i][k] = 0;

		for(int j = 1; j <= n; j++) if(cap[i][j] != 0x3f3f3f3f)

		{

			if(dis[i][k] + cap[i][j] < dis[j][k])

			{

				dis[j][k] = dis[i][k] + cap[i][j];

				if(!vis[j][k])

				{

					Q.push(make_pair(j, k));

					vis[j][k] = 1;

				}

			}

			if(k < m && dis[i][k] + 0 < dis[j][k+1])

			{

				dis[j][k+1] = dis[i][k] + 0;

				if(!vis[j][k+1])

				{

					Q.push(make_pair(j, k+1));

					vis[j][k+1] = 1;

				}

			}

		}

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

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

	//		printf("%d ", dis[j][0]); puts("");

	}

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

		if(dis[n][i] <= C) return i;

}



int main()

{

	while(scanf("%d%d%d", &n, &m, &C) == 3 && (n||m||C))

	{

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

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

		{

			int x, y, z;

			scanf("%d%d%d", &x, &y, &z);

			if(cap[x][y] > z) cap[x][y] = z;

		}

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

	}

	return 0;

}

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





*/