Test Case Tweaking

You are a judge for a programming contest. You are preparing a dataset for a graph problem that asks for the cost of the minimum-cost path. You have generated some random cases, but they are not interesting. You want the answer to be a specific desired value — for instance, the number 2010 representing this year. To do this, you will tweak (adjust) the cost of the minimum-cost path to a given value by changing the costs of some edges, using as few changes as possible.

You are given a non-negative integer $c$ and a directed graph $G$. Each edge of $G$ has a non-negative integer cost. For a path from one node of $G$ to another, the cost of the path is the sum of the costs of the edges on it. For a pair of nodes, the minimum cost between them is the minimum over the costs of all paths connecting them.

Given the graph and two of its nodes — the start node $1$ and the destination node $n$ — you must adjust the edge costs so that the minimum-cost path from node $1$ to node $n$ becomes exactly the target cost $c$. You may assume that $c$ is smaller than the cost of the minimum-cost path between these two nodes in the original graph.

For example, in Figure G.1 the minimum cost of a path from node 1 to node 3 in the given graph is 6. To adjust this minimum cost to 2, we can change the cost of the edge from node 1 to node 3 to 2; after the change that direct edge becomes the minimum-cost path.

For another example, in Figure G.2 the minimum cost of a path from node 1 to node 12 is 4022. To adjust this minimum cost to 2010, we can change the cost of the edge from node 6 to node 12 together with one of the six edges in the right half of the graph. There are many possible edge modifications, but the minimum number of modified edges is 2.

Figure G.1: Example 1 of graph

Figure G.2: Example 2 of graph

The input is a sequence of datasets. Each dataset has the following format.

n m c
f1 t1 c1
f2 t2 c2
.
.
.
fm tm cm

The integers $n$, $m$, and $c$ are the number of nodes, the number of edges, and the target cost, respectively, separated by single spaces, where $2 \le n \le 100$, $1 \le m \le 1000$, and $0 \le c \le 100000$.

Each node of the graph is represented by an integer from $1$ to $n$.

The following $m$ lines describe the edges: the integers $f_i$, $t_i$, and $c_i$ ($1 \le i \le m$) are the originating node, the destination node, and the cost of the $i$-th edge, separated by single spaces. They satisfy $1 \le f_i, t_i \le n$ and $0 \le c_i \le 10000$. You may assume that $f_i \ne t_i$, and that $(f_i, t_i) \ne (f_j, t_j)$ when $i = j$.

For each dataset you may assume that there is at least one path from node $1$ to node $n$, and that the cost of the minimum-cost path from node $1$ to node $n$ in the given graph is greater than $c$.

The end of the input is indicated by a line containing three zeros separated by single spaces.

For each dataset, output on one line the minimum number of edges whose costs must be changed so that the cost of the minimum-cost path from node $1$ to node $n$ equals the target cost $c$. Edge costs cannot be made negative. The output must not contain any other extra characters.