Description

Bessie plans to survey the hay situation of $N$ ($2 \leq N \leq 2\,000$) farms, starting from farm $1$. There are $M$ ($1 \leq M \leq 10^4$) bidirectional roads in total, and the total length of all roads does not exceed $10^9$. There may be multiple roads between some pairs of farms, and all farms are connected.

Bessie wants to compute the length of the longest edge in a minimum spanning tree of this graph.

Input Format

The first line contains two integers $N, M$.

Each of the next $M$ lines contains three space-separated integers $A_i, B_i, L_i$, indicating there is a road between $A_i$ and $B_i$ with length $L_i$.

Output Format

Output a single integer, the length of the longest edge in the minimum spanning tree.

3 3
1 2 23
2 3 1000
1 3 43

43

Hint

Translated by ChatGPT 5