This page is still under construction.

Parts of this page are still being built. What you see may change.

Parade

Time limit2sMemory limit1024 MB

Summary
Choose the fewest directed roads to reverse so that some walk from city 1 to city N uses total length at most L, or report that it is impossible.
Level

Medium7 of 10

Topics
Graph, Shortest path, Dynamic programming, Binary search
Solved
No attempts yet

Problem

In the kingdom of JOI, a marching band parade will be held to celebrate the opening of JOIG.

The kingdom of JOI has N cities, numbered 1 through N. There are also M one-way roads that the marching band can use, numbered 1 through M. Road i (1 ≦ i ≦ M) is a one-way road from city Ai to city Bi with length Ci.

In the parade, the marching band must move so that the following conditions are satisfied.

  • It starts at city 1, repeatedly travels along some roads in their forward direction, and heads for city N.
  • The total length of the roads the marching band travels is at most L.

You, the queen of the kingdom of JOI, realize that there may be no route for the marching band that satisfies these conditions. So, in order to hold the parade, you decide to reverse the direction of 0 or more roads on the day of the parade.

To avoid confusion, you want to reverse as few roads as possible.

Given the information about the cities and roads of the kingdom of JOI and the integer L, determine whether the parade can be held by reversing the direction of some roads, and if it can be held, output the minimum number of roads whose direction must be reversed to hold the parade.

Input

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

N M L
A1 B1 C1
A2 B2 C2
:
AM BM CM

Output

Output to standard output, on a single line, the minimum number of roads whose direction must be reversed to hold the parade. However, if the parade cannot be held no matter how the directions of the roads are reversed, output -1.

Constraints

  • 2 ≦ N ≦ 1 000.
  • 0 ≦ M ≦ 1 000.
  • 1 ≦ L ≦ 1 000 000 000.
  • 1 ≦ Ai ≦ N (1 ≦ i ≦ M).
  • 1 ≦ Bi ≦ N (1 ≦ i ≦ M).
  • Ai ≠ Bi (1 ≦ i ≦ M).
  • (Ai, Bi) ≠ (Aj, Bj) (1 ≦ i < j ≦ M).
  • 1 ≦ Ci ≦ 1 000 000 (1 ≦ i ≦ M).
  • All input values are integers.

Examples5

  1. Example 1

    Input
    3 2 5
2 1 2
2 3 3
    Expected output
    1

  2. Example 2

    Input
    3 1 10
2 1 5
    Expected output
    -1

  3. Example 3

    Input
    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
    Expected output
    0

  4. Example 4

    Input
    5 6 1000000000
5 2 1
2 3 1
3 4 1
4 2 1
2 1 1
1 3 1
    Expected output
    1

  5. Example 5

    Input
    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
    Expected output
    2