题目描述

【Out of Hay S Prim 算法】 Bessie 计划调查 N（2≤N≤2000）个农场的干草情况，它从 1 号农场出发。农场之间总共有 M（1≤M≤10^4 ）条双向道路，所有道路的总长度不超过 10^9 。 有些农场之间存在着多条道路，所有的农场之间都是连通的。 Bessie 希望计算出该图中最小生成树中的最长边的长度。

输入格式

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

输出格式

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

样例

输入样例 1

3 3
1 2 23
2 3 1000
1 3 43

输出样例 1

43

输入样例 2

2 1
1 2 5

输出样例 2

5

输入样例 3

4 5
1 2 10
1 2 5
2 3 8
3 4 7
1 4 20

输出样例 3

8