Турист Гусейн#10202
Гусейн вирішив поїхати до іншої країни, але в сезон коронавірусу складно знайти дешевий маршрут. У водія автобуса є список із міст у його країні, і він підрахував, які маршрути між цими містами принесуть найбільший прибуток. Кожен шлях з'єднує два міста. Вартість шляху — це сума, яку водій отримав би, якщо б обрав даний маршрут.
Необхідно обрати набір шляхів так, щоб будь-які два з них мали спільне місто. Обчисліть максимальну можливу вартість, яку може отримати водій автобуса.
У першому рядку задано два цілих числа: кількість міст n~(1 \le n \le 3 \cdot 10^5) та кількість шляхів m~(1 \le m \le 5 \cdot 10^5). Міста нумеруються числами від до .
Кожен з наступних рядків містить три числа: a_i, b_i~(1 \le a_i, b_i \le n) та p_i~(1 \le p_i \le 10^9 для всіх , де a_i і b_i — це міста, з'єднані -м шляхом, а p_i — вартість цього шляху. Гарантовано, що не існує двох шляхів, які з'єднують одну і ту ж пару міст.
Виведіть одне число — максимально можливу вартість.
Пояснення для першого прикладу
Вибір шляхів 1 - 2, 1 - 3, 1 - 4 дає вартість , і це є правильною відповіддю. Можна також обрати шляхи 1 - 2 ,1 - 4, 2 - 4, але в цьому випадку вартість буде меншою — .