#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
struct Edge{
  int v, cost; //頂点, コスト
  int times; //枝のコストを変えた回数
  Edge(int v, int cost) : v(v), cost(cost) {}
  Edge(int v, int cost, int times) : v(v), cost(cost), times(times) {}
  bool operator < (const Edge& e) const {
    if(times != e.times) return times > e.times;
    return cost > e.cost;
  }
};
typedef vector<Edge> Node;
typedef vector<Node> Graph;

int main(){
  int N, M, C;
  while(cin >> N >> M >> C && N){
    Graph G(N);
    REP(i, M){
      int f, t, c; cin >> f >> t >> c;
      f--; t--;
      G[f].push_back(Edge(t, c));
    }
    priority_queue<Edge> que;
    int dist[100][100] = {};
    REP(i, N)REP(j, N) dist[i][j] = INF;
    que.push(Edge(0, 0, 0));
    dist[0][0] = 0;
    while(!que.empty()){
      int u = que.top().v;
      int cost = que.top().cost;
      int times = que.top().times;
      que.pop();
      if(u == N - 1 && cost <= C) {
        cout << times << endl;
        break;
      }
      if(dist[u][times] < cost) continue;
      FORIT(e, G[u]){
        if(dist[e->v][times] > cost + e->cost){
          dist[e->v][times] = cost + e->cost;
          que.push(Edge(e->v, cost + e->cost, times));
        }
        if(times + 1< N && dist[e->v][times + 1] > cost){
          dist[e->v][times + 1] = cost;
          que.push(Edge(e->v, cost, times + 1));
        }
      }
    }
  }
  return 0;
}