You are given an undirected weighted graph with N vertices numbered from 0 to N-1 and M edges. You are also given a source vertex S and a destination vertex D.

The stress of a path is defined as the maximum edge weight present on that path.

Find the minimum possible stress among all paths from S to D.

---

Input Format

• The first line contains two integers N and M.
• The next M lines contain three integers u, v, and w, representing an undirected edge between u and v with weight w.
• The last line contains two integers S and D.

---

Output Format

Print a single integer — the minimum possible stress required to travel from S to D.

---

Constraints

• 1 ≤ N ≤ 2 × 10^5
• 1 ≤ M ≤ 2 × 10^5
• 0 ≤ u, v < N
• 1 ≤ w ≤ 10^9

---

Example

Input

5 6
0 1 4
1 2 8
0 2 6
2 3 5
3 4 3
1 4 10
0 4

Output

6

Explanation

The path 0 → 2 → 3 → 4 has edge weights {6,5,3}.

Stress = max(6,5,3) = 6, which is the minimum possible.

---