[USACO05MAR] Out of Hay S

题目描述

Bessie 计划调查 $N$($2 \leq N \leq 2\,000$)个农场的干草情况,它从 $1$ 号农场出发。农场之间总共有 $M$($1 \leq M \leq 10^4$)条双向道路,所有道路的总长度不超过 $10^9$。有些农场之间存在着多条道路,所有的农场之间都是连通的。 Bessie 希望计算出该图中最小生成树中的最长边的长度。

输入输出格式

输入格式


第一行两个整数 $N,M$。 接下来 $M$ 行,每行三个用空格隔开的整数 $A_i,B_i,L_i$,表示 $A_i,B_i$ 之间有一条道路,长度为 $L_i$。

输出格式


一个整数,表示最小生成树中的最长边的长度。

输入输出样例

输入样例 #1

3 3
1 2 23
2 3 1000
1 3 43

输出样例 #1

43