E1. Вторжение Далеков (лёгкая)
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
128 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хайди обнаружила, что Далеки создали сеть двусторонних Временных Коридоров, соединяющих различные точки пространства в разные моменты времени. Она подозревает, что они планируют очередное вторжение на всё Пространство и Время. Чтобы противостоять вторжению, она хочет развернуть ловушку во Вихре Времени, вдоль тщательно выбранного Временного Коридора. Хайди знает, что возится с Вихрем Времени опасно, поэтому она решила посоветоваться с Доктором. В результате, она узнала следующее:

  • Разные Временные Коридоры требуют разного количества энергии для поддержания их в стабильном состоянии.
  • Далеки скорее всего не будут использовать все коридоры в своём вторжении. Они выберут набор Коридоров, которые требует минимальной суммы энергии для поддержания и при этом позволяет путешествовать между всеми точками (иначе говоря, они выберут минимальное остовное дерево).
  • Установка ловушки может изменить энергию, необходимую для поддержания коридора стабильным.

Хайди решила провести полевые испытания и развернуть одну ловушку, разместив ее вдоль первого коридора. Но она хочет знать, собираются ли Далеки использовать этот коридор после развёртывания ловушки.

Она дала вам карту Временных Коридоров (представляющую собой неориентированный граф) с требованиями на энергию для каждого Коридора.

Для Коридора $$$c$$$, $$$E_{max}(c)$$$ это наибольшее $$$e \le 10^9$$$, такое что если мы заменим требуемое количество энергии у $$$c$$$ на $$$e$$$, то Далеки возможно воспользуются $$$c$$$ в своём вторжении (иначе говоря, оно будет входить в хотя бы одно минимальное остовное дерево). Вам нужно вычислить $$$E_{max}(c_1)$$$ для Коридора $$$c_1$$$, в котором Хайди хочет разместить ловушку, и которое является первым ребром графа.

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

Первая строка содержит целые числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$n - 1 \leq m \leq 10^6$$$) — количество точек, которые планируется захватить, и количество Временных Коридоров.

Каждая из следующих $$$m$$$ строк задаёт Коридор и состоит из точек $$$a$$$, $$$b$$$ и требуемой энергии $$$e$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$, $$$0 \leq e \leq 10^9$$$).

Гарантируется, что ни одна пара $$$\{a, b\}$$$ не повторится и что граф является связным. Иначе говоря, можно добраться между любыми двумя точками через ноль или более Коридоров.

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

Выведите одно целое число: $$$E_{max}(c_1)$$$ для первого Коридора $$$c_1$$$ из входных данных.

Пример
Входные данные
3 3
1 2 8
2 3 3
3 1 4
Выходные данные
4
Примечание

После установки ловушки новая потребность в энергии для первого Коридора может быть меньше, больше или равна старой потребности в энергии.

В примере, если энергия первого Коридора установлена в $$$4$$$ или меньше, то Далеки могут использовать множество Коридоров $$$\{ \{ 1,2 \}, \{ 2,3 \} \}$$$ (в частности, если установить вес меньше $$$4$$$, то это будет единственным возможным множеством Коридоров). Однако, если энергия будет больше $$$4$$$, то Далеки воспользуются множеством Коридоров $$$\{ \{2,3\}, \{3,1\} \}$$$.