// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <vector>

#include <deque>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

#include <sstream>

#include <numeric>

#include <bitset>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <climits>

#include <cctype>

#include <cassert>

using namespace std;



typedef long long ll;

static const double EPS = 1e-8;

static const double PI = 4.0 * atan(1.0);

bool ISINT(double x){return fabs(x-(int)x)<EPS;}

bool ISEQ(double x,double y){return fabs(x-y)<EPS;}

string itos(ll x){stringstream ss;ss<<x;return ss.str();}

#define REP(i,a,b) for(int i=a;i<b;i++)

#define rep(i,n) REP(i,0,n)

#define EREP(i,a,b) for(int i=a;i<=b;i++)

#define erep(i,n) EREP(i,0,n)

#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)



typedef pair<int,int> P;



class State{

public:

  int id,del,cost;

  State(){}

  State(int _id,int _del,int _cost){

    id = _id;

    del = _del;

    cost = _cost;

  }



  bool operator<(const State &st)const{

    return cost > st.cost;

  }

};



int n,m,c;

vector<P> t[102];



int main(void){

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

    rep(i,n+1) t[i].clear();

    rep(i,m){

      int a,b,c;

      scanf("%d%d%d",&a,&b,&c);

      t[a].push_back(P(b,c));

    }



    priority_queue<State> open;

    bool closed[102][1002];

    open.push(State(1,0,0));

    memset(closed,0,sizeof(closed));



    int ans = INT_MAX;



    while(!open.empty()){

      State st = open.top(); open.pop();

      if(closed[st.id][st.del]) continue;

      closed[st.id][st.del] = true;



      if(st.id == n){

        ans = min(ans,st.del);

        continue;

      }



      rep(i,t[st.id].size()){

        P e = t[st.id][i];

        if(st.cost + e.second <= c && !closed[e.first][st.del]){

          open.push(State(e.first,st.del,st.cost+e.second));

        }

        if(st.del+1 <= m && !closed[e.first][st.del+1]){

          open.push(State(e.first,st.del+1,st.cost));

        }

      }

    }



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

  }

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <string>

#include <vector>

#include <deque>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

#include <sstream>

#include <numeric>

#include <bitset>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <climits>

#include <cctype>

#include <cassert>

using namespace std;



typedef long long ll;

static const double EPS = 1e-8;

static const double PI = 4.0 * atan(1.0);

bool ISINT(double x){return fabs(x-(int)x)<EPS;}

bool ISEQ(double x,double y){return fabs(x-y)<EPS;}

string itos(ll x){stringstream ss;ss<<x;return ss.str();}

#define REP(i,a,b) for(int i=a;i<b;i++)

#define rep(i,n) REP(i,0,n)

#define EREP(i,a,b) for(int i=a;i<=b;i++)

#define erep(i,n) EREP(i,0,n)

#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)



typedef pair<int,int> P;



class State{

public:

  int id,del,cost;

  State(){}

  State(int _id,int _del,int _cost){

    id = _id;

    del = _del;

    cost = _cost;

  }



  bool operator<(const State &st)const{

    return cost > st.cost;

  }

};



int n,m,c;

vector<P> t[102];

bool closed[102][102];



int main(void){

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

    rep(i,n+1) t[i].clear();

    rep(i,m){

      int a,b,c;

      scanf("%d%d%d",&a,&b,&c);

      t[a].push_back(P(b,c));

    }



    priority_queue<State> open;

    open.push(State(1,0,0));

    memset(closed,0,sizeof(closed));



    int ans = INT_MAX;



    while(!open.empty()){

      State st = open.top(); open.pop();

      if(closed[st.id][st.del]) continue;

      closed[st.id][st.del] = true;



      if(st.id == n){

        ans = min(ans,st.del);

        continue;

      }



      rep(i,t[st.id].size()){

        P e = t[st.id][i];

        if(st.cost + e.second <= c && !closed[e.first][st.del]){

          open.push(State(e.first,st.del,st.cost+e.second));

        }

        if(st.del+1 <= n && !closed[e.first][st.del+1]){

          open.push(State(e.first,st.del+1,st.cost));

        }

      }

    }



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

  }

}

// Fastest known solution for this problem: