#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <cstdio>
#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
#define PB push_back
#define MP make_pair
#define MT(a,b,c) MP(a, MP(b, c))
#define T1 first
#define T2 second.first
#define T3 second.second
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int memo[100][100];
vector<vector<PII> > graph;

int main(){
	while(1){
		int n,m,c;
		cin>>n>>m>>c;
		memset(memo, -1, sizeof(memo));
		if(n==0)return 0;
		graph = vector<vector<PII> >(n);
		REP(i,m){
			int x,y,r;
			scanf("%d%d%d", &x,&y,&r);
			x--, y--;
			graph[x].PB(MP(y,r));
		}
		priority_queue<TIII, vector<TIII>, greater<TIII> > q;
		q.push(MT(0, 0, 0));
		while(!q.empty()){
			TIII tmp = q.top();
			q.pop();
			if(memo[tmp.T3][tmp.T1]!=-1)continue;
			memo[tmp.T3][tmp.T1] = tmp.T2;
			if(tmp.T3 == n-1){
				cout << tmp.T1 << endl;
				break;
			}
			REP(i, graph[tmp.T3].size()){
				q.push(MT(tmp.T1+1, tmp.T2, graph[tmp.T3][i].first));
				if(tmp.T2+graph[tmp.T3][i].second <= c)q.push(MT(tmp.T1, tmp.T2+graph[tmp.T3][i].second, graph[tmp.T3][i].first));
			}
		}
	}
}