P83451

最小差值生成树2

难度 7 级 动态树 图论
讨论 统计 2通过 3提交 66.7%通过率 旧版界面
时间限制 1 秒 内存限制 256 MB

题目描述

给定一个点标号从 1 到 n 的、有 m 条边的无向图,求边权最大值与最小值的差值最小的生成树。图可能存在自环。

输入

第一行有两个整数,表示图的点数 n 和边数 m。

接下来 m 行,每行三个整数 u, v, w,表示存在一条连接 u, v 长度为 w 的边。

输出

输出一行一个整数,表示答案。

样例

样例 1
输入
4 6 
1 2 10 
1 3 100 
1 4 90 
2 3 20 
2 4 80 
3 4 40
输出
20

提示

  • 对于 100\% 的数据,保证 1 \leq n \leq 5 \times 10^4,1 \leq m \leq 2 \times 10^5,1 \leq u, v \leq n,1 \leq w \leq 10^4。

来源

luogu

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交