“最小”生成树（mintree）

• 输入：mintree.in
• 输出：mintree.out
• 时间限制：2 s
• 内存限制：512 MB

题目背景

紫晶裂肤，红光未熄。
风雪合拢，封印犹虚。

题目描述

皮耶罗耗尽全力，封印了若娜瓦。然而，若娜瓦封印未固。为稳固封印，需要从由地脉锚点构成的一张带权无向连通图中选出一棵生成树，使树中边权的最大值与最小值之差尽量小。

给定一个 $n$ 个节点、$m$ 条边的无向连通图，每条边有一个正整数权值。

你需要选择图中的 $n-1$ 条边，使得这些边构成一棵生成树，即连接所有 $n$ 个节点且无环。

定义这棵生成树的“极差”为：树中所有边权值的最大值与最小值之差。

求所有生成树中，极差的最小值。

输入格式

从文件 mintree.in 中读入数据。

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示一条连接节点 $u$ 与节点 $v$ 的无向边，边权为 $w$。

输出格式

输出到文件 mintree.out 中。

输出一行一个整数，表示最小极差。

4 5
1 2 1
2 4 3
3 4 2
1 4 4
2 3 5

2

样例1解释

一棵极差为 $2$ 的生成树：边 $(1,2,1)$、$(2,4,3)$、$(3,4,2)$，最大边权 $3$，最小边权 $1$，极差 $2$。

不存在极差为 $1$ 的生成树，因为需要所有边权都在某个长度为 $1$ 的区间内，但图中没有这样的 $3$ 条边能连通所有点。

数据范围

对于所有数据，$2 \le n \le 2 \times 10^5$，$n-1 \le m \le 3 \times 10^5$，$1 \le u,v \le n$，$1 \le w \le 10^9$。每个测试点 $5$ 分。

特殊性质 A：原图是一棵树，即 $m=n-1$。

特殊性质 B：所有边权 $w \in \{1,2\}$。

特殊性质 C：保证存在一种边权 $w$，使得所有权值为 $w$ 的边构成的子图连通。