Taco: Least Maximum Magical Power

In this problem, you are given a network of clearings connected by roads. Each road increases your magical power by a fixed amount. The goal is to find a path from a starting clearing src to a destination clearing dst such that the maximum magical power increase encountered on any road along the path is minimized.

More formally, if a path consists of edges with weights \(w_1, w_2, \dots, w_k\), then its cost is defined as:

\(\max(w_1, w_2, \dots, w_k)\).

You are required to compute the minimum cost among all paths from src to dst. If there is no path available, output -1.

Note: A path where src is equal to dst should have a cost of 0.

inputFormat

The input is read from standard input (stdin) with the following format:

N M
u1 v1 w1
u2 v2 w2
... (M lines in total)
src dst

where:

• N: the number of clearings (nodes),
• M: the number of roads (edges),
• Each of the next M lines contains three integers u, v, and w indicating that there is a road between clearings u and v with a magical power increase of w.
• The final line contains two integers src and dst, representing the starting and destination clearings, respectively.

outputFormat

Output a single integer representing the minimum possible maximum magical power along any path from src to dst. If there is no valid path, output -1.

## sample

5 6
0 1 4
0 2 1
2 1 2
1 3 6
2 4 5
4 3 2
0 3

5