Турист Гусейн
Гусейн вирішив поїхати в іншу країну, але в сезон коронавірусу буде складно знайти дешевий шлях. У водія автобуса є список з 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.