最小建设瓶颈

难度：T2

【知识点：Kruskal最小生成树】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

从原图中选择一棵生成树，使其中最大的单条边权尽可能小，输出这个最小可能的最大边权。这里优化的是最贵的一条边，不是总费用。

输入格式

其中 $n$ 为顶点数，顶点编号为 $1$ 到 $n$；$m$ 为随后给出的带权边条数。每条带权边独占一行，依次为 $u,v,w$，表示从 $u$ 到 $v$ 的边及权值 $w$；无向边可双向通行，有向边只能从 $u$ 到 $v$ 通行。

输入$n$、$m$及$m$条无向带权边，允许重边、自环和负权。

规则说明

生成树是选取原图中的一部分边，使所有顶点连通且不形成环；费用为选中边的权值之和。最小生成树是在所有生成树中总费用最小的一个。只有一个顶点时，不选边即可形成生成树，费用为 $0$。

输出格式

在全部生成树中，使最大边权尽量小，输出该最大边权；不存在输出IMPOSSIBLE；$n=1$输出$0$。

数据范围

$1\le n\le 100000$，$0\le m\le 200000$，$|w|\le 10^9$，端点在$1$..$n$。

样例输入

1 1
1 1 -10

样例输出

0

样例输入 2

3 3
1 2 2
2 3 5
1 3 4

样例输出 2

4

样例说明 2

选择边权 $2,4$ 可以连通三个点，最大边权为 $4$；只使用小于 $4$ 的边无法连通。