Гусейн решил поехать в другую страну, но в сезон коронавируса будет сложно найти дешевую дорогу. У водителя автобуса есть список из N городов в его стране, и он подсчитал, какие маршруты между этими городами принесут больше денег. Каждый путь соединяет два города. Стоимость пути - это то, сколько заработал бы водитель автобуса, выбрав этот путь. Путь должен быть выбран так, чтобы любые два пути имели общий город. Рассчитайте максимальную стоимость, которую может получить водитель автобуса.

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

В первой строке указано количество городов N (1 ≤ N ≤ 300000) и количество путей M (1 ≤ M ≤ 500000). Номера городов от 1 до N. Следующие M строк содержат по три числа — ai , bi. (1 ≤ ai, bi ≤ N) и pi (1 ≤ pi ≤ 1000000000 для всех i), где ai и bi - два города, соединенных i-м путем, а pi - стоимость пути. Не существует двух путей, соединяющих одну и ту же пару городов.

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

Выведите единственное число: максимально возможную стоимость.

Объяснение для первого примера

Выбрав пути 1–2, 1–3, 1–4 даст стоимость 4 и это правильный ответ. Вы можете выбрать 1–2 ,1–4, 2–4 также , но стоимость будет меньше – 3 .