Alley Boss Hoseok - Efficiency 1

In his youth, Hoseok lived the life of an alley boss. The village where Hoseok lived had N intersections and M alleys. Intersections are numbered from 1 to N. An alley connects two different intersections in both directions, and there is at most one alley between any two intersections. Hoseok, who uses doppelganger techniques, placed a copy of himself in every alley, and each copy will collect a toll from anyone who passes through. The toll can differ from alley to alley.

You want to travel from intersection A to intersection B carrying C won. Seeing Hoseok's tyranny is annoying, but since there is no way to beat his doppelganger technique, you decide to pay and go. Still, since you have to pass through anyway, you want to feel as little shame as possible. The shame you feel is proportional to the largest amount you paid along the path, so among the various ways you can go, you want to receive the least shame. That is, you want to minimize the maximum toll you must pay on any single alley.

For example, suppose there are 5 intersections and 5 alleys as in the figure above, and you want to go from intersection 1 to intersection 3. If you start with 10 won, there are 2 possible paths. Going 1 -> 2 -> 3 requires 10 won in total, and the maximum toll along the way is 5 won; going 1 -> 4 -> 5 -> 3 requires 8 won in total, and the maximum toll is 6 won. The path with the least shame is the one whose maximum toll is 5. But if you have only 8 won, the former path is impossible, so the best choice is to take the path whose maximum toll is 6.

From the example above, you have learned that the more you want to reduce shame, the more money you need (or the same amount), and that accepting more shame requires less money (or the same amount). Given the map of the village and the toll Hoseok collects in each alley, compute the minimum possible value of the maximum toll you must pay on any single alley. If you absolutely cannot reach the destination with the money you have, print -1.

The first line gives the number of intersections N, the number of alleys M, the starting intersection number A, the destination intersection number B, and the money you have C, separated by spaces. The next M lines each give the numbers of the two intersections connected by an alley and the toll of that alley, separated by spaces. An alley between the same pair of intersections is given at most once, and alleys are bidirectional.

Among all paths from the starting intersection to the destination intersection that cost at most C won using the alleys Hoseok guards, print the minimum value of the maximum toll along the path. If no such path exists, print -1.

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 500,000
• 1 ≤ C ≤ 2,000,000
• 1 ≤ toll per alley ≤ 20
• 1 ≤ A, B ≤ N, A ≠ B
• The intersections connected by an alley have different numbers.