题目描述

Bessie计划调查N个农场的干草情况，它从1号农场出发。农场之间总共有M条双向道路，有些农场之间存在着多条道路，所有的农场之间都是连通的。

Bessie 希望计算出该图中最小生成树中的最长边的长度。

输入格式

第一行两个整数N(2≤N≤2000)，MM(1≤M≤10^4)。

接下来M行，每行三个用空格隔开的整数Ai，Bi，Li，表示Ai、Bi之间有一条道路，长度为Li。所有道路的总长度不超过10^9。

输出格式

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

输入/输出样例

3 3
1 2 23
2 3 1000
1 3 43

43

说明/提示

时间1000ms，内存256MiB