#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#ifdef BTK
#include<dvector.h>
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww{cww(){
    CIN_ONLY{
        ios::sync_with_stdio(false);cin.tie(0);
    }
}}star;
#define DEBUG if(0)
#endif

#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
int N,M;
LL C;

typedef LL FTYPE;
struct edge{
    FTYPE flow;
    int to,rev;
};
typedef vector<edge> E;
typedef vector<E> Graph;
void addedge(Graph&g,int from,int to,FTYPE f){
    int x=g[from].size();
    int y=g[to].size();
    g[from].pb(edge{f,to,y});
    g[to].pb(edge{(FTYPE)0,from,x});
}

vector<int> bfs(Graph& G,int s){
    int N = G.size();
    queue<int> que;
    vector<int> dist(N,-1);
    dist[s] = 0;
    que.push(s);
    for(;!que.empty();que.pop()){
        auto v=que.front();
        for(auto& e : G[v])
            if(e.flow>0&&dist[e.to]==-1){
                dist[e.to] = dist[v] + 1;
                que.push(e.to);
        }
    }
    return dist;
}

FTYPE maxflow(Graph& G,int s,int t){
    FTYPE res=0;
    int N = G.size();
    while(true){
        auto dist = bfs(G,s);
        if(dist[t] < 0)break;
        vector<unsigned> iter(N,0);
        std::function<FTYPE(int,FTYPE)> dfs=[&](int v,FTYPE f){
            if(v==s)return f;
            for(auto &i = iter[v]; i < G[v].size(); i++){
                edge &e = G[v][i];
                edge &re = G[e.to][e.rev];
                if(re.flow>0 && dist[v] >dist[e.to]){
                    FTYPE d=dfs(e.to,min(f,re.flow));
                    if(d>0){e.flow+=d;re.flow-=d;return d;}
                }
            }
            return (FTYPE)0;
        };
        FTYPE f;
        while((f=dfs(t,114514))> 0)res+=f;
    }
    return res;
}

typedef vector<LL> V;
typedef vector<V> VV;
int s[1123];
int t[1123];
LL c[1123];

void solve(){
    Graph g(N);
    VV gg(N);
    VV d(N,V(N,C+1));
    VV dist(N,V(M+1,C+1));
    REP(i,M){
        cin>>s[i]>>t[i]>>c[i];
        s[i]--;t[i]--;
        chmin(d[s[i]][t[i]],c[i]);
    }
    REP(i,N)d[i][i]=0;
    REP(k,N)REP(i,N)REP(j,N)chmin(d[i][j],d[i][k]+d[k][j]);
    REP(i,M){
        if(d[0][s[i]]+c[i]+d[t[i]][N-1]<C)addedge(g,s[i],t[i],1);
        gg[s[i]].pb(i);
    }
    using P = tuple<LL,int,int>;
    priority_queue<P,vector<P>,greater<P>> que;
    que.push(P(0ll,0,0));
    dist[0][0]=0;
    while(que.size()){
        LL cost;int v,cnt;
        tie(cost,v,cnt) = que.top();que.pop();
        if(dist[v][cnt]<cost)continue;
        for(auto &e:gg[v]){
            int u = t[e];
            LL nxtcost = cost + c[e];
            if(cnt<M)if(chmin(dist[u][cnt+1],cost))que.push(P(cost,u,cnt+1));
            if(chmin(dist[u][cnt],nxtcost))que.push(P(nxtcost,u,cnt));
        }
    }
    LL ret = M;
    REP(i,M+1)if(dist[N-1][i]<=C)chmin(ret,(LL)i);
    cout<<maxflow(g,0,N-1)+ret<<endl;
}
int main(){
    while(cin>>N>>M>>C,N)solve();
    return 0;
}

Measured memory_bytes: 6944