Parade

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

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

In the parade, the drum and bugle corps must move under the following conditions.

• Start from city 1 and proceed along the direction of some roads, repeating this, to reach city N.
• The sum of the lengths of the roads traveled by the drum and bugle corps is at most L.

You, the queen of the Kingdom of JOI, realized that there might be no route for the drum and bugle corps that satisfies these conditions. Therefore, to hold the parade, you decided to reverse the direction of travel of zero or more roads on the day of the parade.

To avoid confusion, you want to minimize the number of roads whose direction of travel is reversed.

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

Constraints

• 2 ≦ N ≦ 1000.
• 0 ≦ M ≦ 1000.
• 1 ≦ L ≦ 1000000000.
• 1 ≦ A_i ≦ N (1 ≦ i ≦ M).
• 1 ≦ B_i ≦ N (1 ≦ i ≦ M).
• A_i ≠ B_i (1 ≦ i ≦ M).
• (A_i, B_i) ≠ (A_j, B_j) (1 ≦ i < j ≦ M).
• 1 ≦ C_i ≦ 1000000 (1 ≦ i ≦ M).
• All input values are integers.

Input

The input is given from standard input in the following format.
N M L
A₁ B₁ C₁
A₂ B₂ C₂
:
A_M B_M C_M

Output

Output the minimum number of roads whose direction of travel must be reversed to hold the parade in one line to standard output. If it is impossible to hold the parade no matter how the directions of travel are reversed, output -1.

Sample Input and Output

Sample Input 1

3 2 5
2 1 2
2 3 3

Sample Output 1

1

By reversing the direction of travel of road 1, the parade can be held.

Since this is the minimum value, output 1.

Sample Input 2

3 1 10
2 1 5

Sample Output 2

-1

Since it is impossible to hold the parade no matter how the directions of travel are reversed, output -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

---