P1547 [USACO05MAR] Out of Hay S

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.

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 a single integer, the length of the longest edge in the minimum spanning tree.

Translated by ChatGPT 5