Alley Boss Hoseok - Feasibility

In his younger days, Hoseok lived as an alley boss. The village where Hoseok lived has N intersections and M alleys. Intersections are numbered from 1 to N. An alley connects two distinct intersections in both directions, and at most one alley connects any pair of intersections. Hoseok, who uses clone techniques, placed a clone in every alley, and each clone collects a toll from anyone who passes through. The toll may differ from alley to alley.

You want to travel from intersection A to intersection B carrying C won. Hoseok's tyranny is irritating, but there is no way to beat his clones, so you decide to pay and go. Still, since you have to pass through anyway, you want to suffer the least humiliation. The humiliation you feel is proportional to the largest amount you pay along the path, so among the various ways to go you want to take the one with the least humiliation. That is, you want to minimize the maximum toll you have to pay on a 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 two paths. Going 1 -> 2 -> 3 requires 10 won in total, and the largest toll along the way is 5 won; going 1 -> 4 -> 5 -> 3 requires 8 won in total, and the largest toll is 6 won. The path with the least humiliation 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 can see that reducing humiliation requires the same amount of money or more, and accepting more humiliation requires the same amount of money or less. Given the village map and the toll Hoseok collects on each alley, compute the minimum possible value of the maximum toll you must pay on 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 start intersection A, the destination intersection B, and the money you have C, separated by spaces. The next M lines each give the numbers of the two intersections an alley connects 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 the paths from the start intersection to the destination intersection that cost at most C won through the alleys Hoseok guards, print the minimum possible value of the maximum toll along the path. If no such path exists, print -1.

• 1 ≤ N ≤ 10
• 1 ≤ M ≤ N × (N-1) / 2
• 1 ≤ C ≤ 10,000
• 1 ≤ toll per alley ≤ 1,000
• 1 ≤ A, B ≤ N, A ≠ B
• The two intersections an alley connects have different numbers.