194. Разделение графа

Дан взвешенный неориентированный граф $G$, содержащий $n$ вершин и $m$ рёбер.

Разбейте вершины графа на два не пустых множества так, чтобы ребро минимального веса, соединяющее вершины из одного множества, имело максимально большой вес.

Гарантируется, что граф не содержит петель и его нельзя разбить так, чтобы такого ребра не существовало.

В первой строке задано число вершин $n$ ($3 \leq n \leq 10^5$) и число ребер $m$ ($3\leq m \leq 10^5$) графа.

В следующих $m$ строках заданы ребра в формате $u$, $v$, $w$ ($1\leq u, v \leq n$, $u\neq v$, $1 \leq w \leq 10^5$), где $u$ и $v$ задают начальную и конечную вершину ребра, а $w$ — его вес.

В единственной строке выведите максимальный возможный вес ребра, которое имеет минимальный вес среди тех, что соединяют вершины принадлежащие одному множеству.

Рассмотрим первый пример из условия. В нём возможно всего 3 различных разбиения удовлетворяющих условию, рассмотрим каждое из них:

• $\{\{1, 2\}, \{3\}\}$

  , в таком случае рёбра $1$ и $2$ будут будут соединять вершины из одного множества, то есть ответ $1$;

• $\{\{1, 3\}, \{2\}\}$

  , в таком случае только ребро $3$ будет соединять вершины из одного множества, то есть ответ $3$;

• $\{\{2, 3\}, \{1\}\}$

  , в таком случае только ребро $4$ будет соединять вершины из одного множества, то есть ответ $4$.

Получаем, что ответ на тест, достигается при третьем варианте разбиения.

Во втором тесте ответ достигается на разбиении $\{\{1, 3\}, \{2, 4\}\}$. Легко убедиться расписав все различные разбиения, что не существует разбиения данного графа, на котором ответ был бы больше.