import std.stdio;
import std.ascii;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;

struct Edge {
    int to, cost;
}

const INF = 1<<28;

int N, M, C;
Edge[][] G;
bool input() {
    scanf("%d %d %d\n", &N, &M, &C);
    if (N == 0 && M == 0 && C == 0) return false;
    G = new Edge[][N];
    foreach (i; 0 .. M) {
        int f, t, c;
        scanf("%d %d %d\n", &f, &t, &c);
        f--; t--;
        G[f] ~= Edge(t, c);
    }
    return true;
}

struct P {
    int k, v;
}

struct S {
    int k, v, cost;
}

void solve() {
    //writeln([N, M, C]);
    int[P] D;
    BinaryHeap!(Array!S, "a.k == b.k ? a.cost > b.cost : a.k > b.k") PQ;
    PQ.insert(S(0, 0, 0));
    while (!PQ.empty) {
        S cur = PQ.front; PQ.removeFront;
        //writeln(cur);
        if (cur.v == N - 1 && cur.cost <= C) {
            writeln(cur.k);
            return;
        }
        foreach (e; G[cur.v]) {
            auto next = S(cur.k, e.to, cur.cost + e.cost);
            if (D.get(P(next.k, next.v), INF) > next.cost) {
                D[P(next.k, next.v)] = next.cost;
                PQ.insert(next);
            }
            next = S(cur.k + 1, e.to, cur.cost);
            if (D.get(P(next.k, next.v), INF) > next.cost) {
                D[P(next.k, next.v)] = next.cost;
                PQ.insert(next);
            }
        }
    }
}

void main() {
    while (input) solve;
}