Description

iPig has arrived at the legendary Magic Pig Academy for a two-month training program. After one week of theory and one week of basic magic, iPig has learned a lot about the fundamentals of the pig world: as everyone knows, the world is made of elements; elements can be transformed into one another; energy is conserved $\ldots$

Today iPig is taking a tricky test. From previous learning, iPig already knows many kinds of elements and has learned spells that can transform these elements, each consuming some energy. As a top student from PKU, using the least energy to transform one element into another $\ldots$ well, iPig’s magic instructor isn’t that naive! This time, the instructor has brought many samples of element $1$ and requires iPig to transform them one by one into element $N$ using learned spells. To make it harder, each sample must follow a different conversion process. This seemingly difficult task is actually not a challenge for iPig, because he has a solid backup $\ldots$ you!

Note that there can be multiple spells for transforming between two elements, and transformations are one-way. During a conversion, an element (including the starting element) may be visited multiple times, but once the target element is reached, that sample’s conversion process ends. iPig’s total energy is limited, so the maximum number of samples he can convert is finite. See the example for details.

Input Format

The first line contains three numbers $N, M, E$, representing the number of known elements (numbered from $1$ to $N$), the number of learned spells, and iPig’s total energy.

Then follow $M$ lines, each containing three numbers $s_i, t_i, e_i$, indicating a known spell that transforms element $s_i$ to element $t_i$ while consuming energy $e_i$.

Output Format

Output a single integer: the maximum number of distinct conversion processes that can be completed. The input guarantees that at least one way exists.

4 6 14.9
1 2 1.5
2 1 1.5
1 3 3
2 3 1.5
3 4 1.5
1 4 1.5

3

Hint

There are $4$ meaningful conversion processes:

$1\to 4$, consuming energy $1.5$.

$1\to 2\to 1\to 4$, consuming energy $4.5$.

$1\to 3\to 4$, consuming energy $4.5$.

$1\to 2\to 3\to 4$, consuming energy $4.5$.

Clearly, at most $3$ of these conversion processes can be completed (choose the first one, and any two of the remaining three), i.e., at most $3$ samples can be converted.

If $E=14.9$ is changed to $E=15$, then all of the above processes can be completed, and the answer becomes $4$.

Input Format

Output Format

Hint

Constraints

• At least $10\%$ of the total score: $N \leq 6$, $M \leq 15$.
• At least $20\%$ of the total score: $N \leq 100$, $M \leq 300$, $E \leq 100$, and $E$ and all $e_i$ are integers (they can be read as integer types directly).
• For all testdata: $2 \leq N \leq 5000$, $1 \leq M \leq 200000$, $1 \leq E \leq 10^7$, $1 \leq e_i \leq E$, and $E$ and all $e_i$ are real numbers.

Data Update Log

• 2010/xx/xx: Original testdata.
• 2018/03/02:
  /user/9168
  of testdata](/discuss/35616).
• 2018/04/20:
  /user/25188
  of testdata](/discuss/40205).
• 2021/01/08:
  /user/215697
  ets of testdata](/discuss/291028).

Translated by ChatGPT 5