Problem Description

In the Kingdom of JOI, a parade of drum and bugle corps is being held to commemorate the JOIG.

The Kingdom of JOI has $ N $ cities numbered from $ 1 $ to $ N $. There are also $ M $ one-way roads that the drum and bugle corps can travel on, numbered from $ 1 $ to $ M $. Road $ i $ ($1 \leq i \leq M$) is a one-way road from city $ A_i $ to city $ B_i $ with a length of $ C_i $.

For the parade, the drum and bugle corps must move under the following conditions:

• Start from city $ 1 $ and repeatedly travel along some roads towards city $ N $.
• The total length of the roads taken by the drum and bugle corps must be $ L $ or less.

You, the queen of the Kingdom of JOI, have realized that there might not be any path for the drum and bugle corps that satisfies these conditions. Therefore, you have decided to reverse the direction of some roads (between $ 0 $ and $ M $) on the day of the parade to avoid confusion.

To minimize confusion, you want to reverse the direction of as few roads as possible.

Given the information about the cities and roads in the Kingdom of JOI and the integer $ L $, determine whether it is possible to hold the parade by reversing the direction of some roads. If it is possible, output the minimum number of roads whose direction needs to be reversed.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ L $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $\vdots$ $ A_M $ $ B_M $ $ C_M $

Output Format

Output the minimum number of roads whose direction needs to be reversed to hold the parade on a single line to the standard output. If it is impossible to hold the parade no matter how the directions are reversed, output -1.

Sample Input and Output

Sample Input #1

3 2 5
2 1 2
2 3 3

Sample Output #1

1

Sample Input #2

3 1 10
2 1 5

Sample Output #2

-1

Sample Input #3

4 8 11
3 1 6
1 3 6
2 4 3
4 2 3
4 3 6
3 4 6
2 1 5
1 2 5

Sample Output #3

0

Sample Input #4

5 6 1000000000
5 2 1
2 3 1
3 4 1
4 2 1
2 1 1
1 3 1

Sample Output #4

1

Sample Input #5

6 15 777777
1 3 497295
4 1 422722
4 5 607164
2 3 135688
5 2 995652
5 1 670296
3 1 138860
4 6 736614
6 3 620085
2 1 796353
6 4 949756
4 2 750680
6 5 591550
5 3 229431
3 2 668173

Sample Output #5

2

Notes/Hints

Constraints

• $2 \leq N \leq 1,000$.
• $0 \leq M \leq 1,000$.
• $1 \leq L \leq 1,000,000,000$.
• $1 \leq A_i \leq N$ ($1 \leq i \leq M$).
• $1 \leq B_i \leq N$ ($1 \leq i \leq M$).
• $A_i \neq B_i$ ($1 \leq i \leq M$).
• $(A_i, B_i) \neq (A_j, B_j)$ ($1 \leq i < j \leq M$).
• $1 \leq C_i \leq 1,000,000$ ($1 \leq i \leq M$).
• All input values are integers.

Subtasks

1. ($ 7 $ points) $ M = N - 1 $, $ (A_i, B_i) = (i, i + 1) $ or $ (A_i, B_i) = (i + 1, i) $ ($1 \leq i \leq M$).
2. ($ 14 $ points) $ M $ is even, $ A_{2i - 1} = B_{2i} $, $ A_{2i} = B_{2i - 1} $, $ C_{2i - 1} = C_{2i} $ ($1 \leq i \leq \frac{M}{2}$).
3. ($ 18 $ points) $N \leq 15$, $M \leq 15$.
4. ($ 20 $ points) $ C_i = 1 $ ($1 \leq i \leq M$), $ L = 1,000,000,000 $.
5. ($ 20 $ points) $ C_i = 1 $ ($1 \leq i \leq M$).
6. ($ 21 $ points) No additional constraints.

Grading Notes

All submissions are graded on the judge system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test inputs corresponding to that subtask.

The score for each submission is the sum of the scores of the subtasks it correctly solves.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked under the "My Score Status" tab in the "Submission Results".

Sample Explanation 1

Reversing the direction of road $ 1 $ allows the parade to be held. This is the minimum, so output $ 1 $. This input example satisfies the constraints of subtasks $ 1, 3, 6 $.

Sample Explanation 2

No matter how the directions of the roads are reversed, the parade cannot be held, so output -1. This input example satisfies the constraints of subtasks $ 3, 6 $.

Sample Explanation 3

This input example satisfies the constraints of subtasks $ 2, 3, 6 $.

Sample Explanation 4

This input example satisfies the constraints of subtasks $ 3, 4, 5, 6 $.

Sample Explanation 5

This input example satisfies the constraints of subtasks $ 3, 6 $.

见题面 Input 部分

见题面 Output 部分