Minimize Path Value

The cost of a path in an undirected graph is the largest edge weight on the path; find the minimum cost from source to destination, and output −1 if they are not connected. Added by this site: when source=destination, the empty path has cost 0. Self-loops and parallel edges may appear.

输入格式

The input gives N M, then M lines of u v weight, then source and destination. Original bounds: M is 1..100000, edge weights are 0..10^9, and labels are 1..N. The original upper bound of N was written as 10⁵5, with an extra 5; this site openly adopts the lenient upper bound 1≤N≤10^55 to cover the common readings of that corrupted notation, without claiming it is the source's definitive original bound. Large labels are read as decimal integers, and only the nodes that appear are stored.

输出格式

Output one integer answer.

样例 1

输入：

4 4
2 1 100
2 3 200
1 4 10
4 3 20
1
3

输出：

20

样例 2

输入：

10000000000000000000000000000000000000000000000000000000 1
1 2 7
1
10000000000000000000000000000000000000000000000000000000

输出：

-1

样例 3

输入：

1 1
1 1 9
1
1

输出：

0

样例说明

The outputs of the three public examples are, in order: 20; -1; 0. They have been checked by independent enumeration or direct simulation.