1931 - 【基础】最小生成树的最长边

题目描述

Bessie 计划调查 N2≤N≤2000)个农场的干草情况,他从 1 号农场出发。农场之间总共有 M1≤M≤10^4)条双向道路,所有道路的总长度不超过 10^9。有些农场之间存在着多条道路,所有的农场之间都是连通的。

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

输入

第一行两个整数 N,M

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

输出

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

样例

输入

3 3
1 2 23
2 3 1000
1 3 43

输出

43
来源

USACO 并查集

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 13
通过人数 9
金币数量 2 枚
统计
上一题 下一题