Test Case Tweaking#3465

Test Case Tweaking

5 seconds

32 megabytes

Easy

You are a judge of a programming contest. You are preparing a dataset for a graph problem to seek for the cost of the minimum cost path. You've generated some random cases, but they are not interesting. You want to produce a dataset whose answer is a desired value such as the number representing this year $2010$ . So you will tweak (which means 'adjust') the cost of the minimum cost path to a given value by changing the costs of some edges. The number of changes should be made as few as possible.

A non-negative integer $c$ and a directed graph $G$ are given. Each edge of $G$ is associated with a cost of a non-negative integer. Given a path from one node of $G$ to another, we can define the cost of the path as the sum of the costs of edges constituting the path. Given a pair of nodes in $G$ , we can associate it with a non-negative cost which is the minimum of the costs of paths connecting them.

Given a graph and a pair of nodes in it, you are asked to adjust the costs of edges so that the minimum cost path from one node to the other will be the given target cost $c$ . You can assume that $c$ is smaller than the cost of the minimum cost path between the given nodes in the original graph.

For example, in Figure 1, the minimum cost of the path from node $1$ to node $3$ in the given graph is $6$ . In order to adjust this minimum cost to $2$ , we can change the cost of the edge from node $1$ to node $3$ to $2$ . This direct edge becomes the minimum cost path after the change.

For another example, in Figure 2, the minimum cost of the path from node $1$ to node $12$ in the given graph is $4022$ . In order to adjust this minimum cost to $2010$ , we can change the cost of the edge from node $6$ to node $12$ and one of the six edges in the right half of the graph. There are many possibilities of edge modification, but the minimum number of modified edges is $2$ .

Input

The input is a sequence of datasets. Each dataset is formatted as follows.

$n$ $m$ $c$ $f_{1}$ f_1 $t_{1}$ t_1 $c_{1}$ c_1 $f_{2}$ f_2 $t_{2}$ t_2 $c_{2}$ c_2 ... $f_{m}$ f_m $t_{m}$ t_m $c_{m}$ c_m

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

Each node in the graph is represented by an integer $1$ through $n$ .

The following $m$ lines represent edges: the integers $f_{i}$ f_i, $t_{i}$ t_i and $c_{i}$ c_i ( $1 \leq i \leq m$ 1 \le i \le m) are the originating node, the destination node and the associated cost of the $i$ -th edge, each separated by a single space. They satisfy $1 \leq f_{i}, t_{i} \leq n$ 1 \le f_i, t_i \le n and $0 \leq c_{i} \leq 10000$ 0 \le c_i \le 10000. You can assume that $f_{i} \neq = t_{i}$ f_i \neq t_i and $(f_{i}, t_{i}) \neq = (f_{j}, t_{j})$ (f_i, t_i) \neq (f_j, t_j) when $i \neq = j$ i \neq j.

You can assume that, for each dataset, 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$ of the given graph is greater than $c$ .

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

Output

For each dataset, output a line containing the minimum number of edges whose cost(s) should be changed in order to make the cost of the minimum cost path from node $1$ to node $n$ equal to the target cost $c$ . Costs of edges cannot be made negative. The output should not contain any other extra characters.

Examples

Example 1