Гусейн решил поехать в другую страну, но в сезон коронавируса будет сложно найти дешевую дорогу. У водителя автобуса есть список из N городов в его стране, и он подсчитал, какие маршруты между этими городами принесут больше денег. Каждый путь соединяет два города. Стоимость пути - это то, сколько заработал бы водитель автобуса, выбрав этот путь. Путь должен быть выбран так, чтобы любые два пути имели общий город. Рассчитайте максимальную стоимость, которую может получить водитель автобуса.
####Входные данные:В первой строке указано количество городов N (1 ≤ N ≤ 300000) и количество путей M (1 ≤ M ≤ 500000). Номера городов от 1 до N. Следующие M строк содержат по три числа — a[i]
, b[i]
. (1 ≤ a[i]
, b[i]
≤ N) и p[i]
(1 ≤ p[i]
≤ 1000000000 для всех i), где a[i]
и b[i]
- два города, соединенных i-м путем, а p[i]
- стоимость пути. Не существует двух путей, соединяющих одну и ту же пару городов.
####Выходные данные:Выведите единственное число: максимально возможную стоимость.
####Объяснение для первого примера
Выбрав пути 1–2, 1–3, 1–4 даст стоимость 4 и это правильный ответ. Вы можете выбрать 1–2 ,1–4, 2–4 также , но стоимость будет меньше – 3 .