406798: GYM102558 E Разделение графа

E. Разделение графаограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Дан взвешенный неориентированный граф $$$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 4
1 2 1
1 2 2
1 3 3
3 2 4

Выходные данные

4

Входные данные

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

Выходные данные

2

Примечание

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

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

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

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