#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define EACH(t,i,c) for(t::iterator i=(c).begin(); i!=(c).end(); ++i)
const double EPS = 1e-10;
const double PI  = acos(-1.0);

	int n,m,c;
struct node{
    int index,cnt,cost;
    node(int index,int cnt,int cost):index(index),cnt(cnt),cost(cost){}
    bool operator<(const node& other)const{
        return cost>other.cost;
    }
};
const int MAX=INT_MAX/10;
const int NONE=-1;

int main(){
	while(cin>>n>>m>>c,n){
		vvi dist(n,vi(n,MAX));
		REP(i,m){
			int f,t,cc;
			cin>>f>>t>>cc;
			dist[f-1][t-1]=cc;
		}
        priority_queue<node> q;
        q.push(node(0,0,0));
        vvi cost(n,vi(m+1,MAX));
        cost[0][0]=0;
        while(!q.empty()){
            node cnode=q.top();q.pop();
            if(cost[cnode.index][cnode.cnt]<cnode.cost){
                continue;
            }
			REP(i,n){
				if(dist[cnode.index][i]!=MAX){
					REP(j,2){
						int newcost=cost[cnode.index][cnode.cnt]+(j?dist[cnode.index][i]:0);
						if(newcost<=c&&cnode.cnt+(1-j)<m+1&&newcost<cost[i][cnode.cnt+(1-j)]){
							cost[i][cnode.cnt+(1-j)]=newcost;
							q.push(node(i,cnode.cnt+(1-j),newcost));
						}
					}
				}
			}
        }
		int ans=MAX;
		REP(i,m+1){
			if(cost[n-1][i]<=c){
				ans=i;
				break;
			}
		}
		cout<<ans<<endl;
	}
}