Саймон Павук
У задачі Комар ви дізналися, що потенційні репродуктивні можливості комах дуже високі. На щастя для нас, людей, у комах є природні вороги, які допомагають зменшити їхню популяцію. Павуки належать до найвідоміших хижаків комах, тому не дивно, що ми включили їх у цей набір задач.
Саймон Павук цього літа з'їв багато комах і розтовстів. Нитки його павутини скоро стануть занадто тонкими, щоб витримати його, і тому йому потрібно їх зміцнити. Оскільки товсті павуки також ліниві, Саймон хоче використати якомога менше матеріалу — адже павуки повинні самі виробляти матеріал для будівництва павутин. Нарешті, він вирішив зміцнити лише деякі з ниток, але важливо, щоб кожен вузол його павутини був досяжний через зміцнені зв'язки.
Крім того, Саймон планує провести свій вільний час на одному з укріплених зв'язків, і він хоче, щоб цей один зв'язок був довгим. Тому, при обчисленні загальної довжини всіх укріплених зв'язків, довжина найдовшого укріпленого зв'язку буде відніматися замість додавання. Допоможіть Саймону вирішити, які зв'язки слід зміцнити, щоб мати найменшу можливу загальну довжину за цих умов.
Вхідні дані
Вхідні дані складаються з описів кількох павутин. Перша строка кожного опису містить два числа: кількість N (2 ≤ N ≤ 2000) вузлів у павутині та кількість M (0 ≤ M ≤ 1000000) зв'язків між парами вузлів. Кожна з наступних M строк описує один зв'язок. Опис кожного зв'язку містить три додатні цілі числа u_i, v_i, i, де u_i і v_i (1 ≤ u_i, v_{i }≤ N і u_i ≠ v_i) є двома вузлами, з'єднаними зв'язком, а i є його довжиною (1 ≤ i ≤ 100000).
Вихідні дані
Для кожної павутини виведіть один рядок з мінімально можливою загальною довжиною укріплених зв'язків за всіх заданих умов. Пам'ятайте, що загальна довжина — це сума довжин всіх укріплених зв'язків мінус подвоєна довжина найдовшого укріпленого зв'язку.
Якщо неможливо досягти кожного вузла з кожного іншого вузла через послідовність зв'язків, то виведіть "disconnected" замість вартості.