Alley Boss Hoseok - Efficiency 2

In his younger days, 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 at most one alley connects any given pair of intersections. Hoseok, who can create clones of himself, placed a clone in every alley, and each clone will collect a toll from anyone passing through. The toll can differ from alley to alley.

You want to travel from intersection A to intersection B with C won in your pocket. Watching Hoseok's tyranny is annoying, but you have no way to beat his cloning technique, so you will pay and go. Still, since you have to pass through anyway, you want to suffer the least shame. The shame you feel is proportional to the largest amount you paid along the path, so among all the possible ways you can go, you want to feel the least shame. In other words, you want to minimize the maximum toll you have to pay at 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 paths you can take. Going 1 -> 2 -> 3 takes 10 won in total and the largest toll along the way is 5 won, while going 1 -> 4 -> 5 -> 3 takes 8 won in total and the largest toll is 6 won. The path with the least shame is the one whose largest toll is 5. But if you have only 8 won, the former path is impossible, so the best you can do is take the path whose largest toll is 6.

From the example above, you have learned that the more you want to reduce shame, the same or more money is needed, and if you accept more shame, the same or less money is needed. 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 at a 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 following M lines each give the numbers of the two intersections an alley connects and the toll of that alley, separated by spaces. An alley connecting 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 C won or less through 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 ≤ 10^14
• 1 ≤ toll per alley ≤ 10^9
• 1 ≤ A, B ≤ N, A ≠ B
• The two intersections an alley connects are different.