Саймон Паук
В задаче Комар вы узнали, что насекомые обладают высокой репродуктивной способностью. К счастью, у них есть естественные враги, которые помогают контролировать их численность. Пауки — одни из самых известных хищников насекомых, поэтому неудивительно, что они включены в этот набор задач.
Саймон Паук этим летом съел много насекомых и стал полнее. Его паутина вскоре может не выдержать его веса, поэтому он решил укрепить её. Поскольку толстые пауки также ленивы, Саймон хочет использовать как можно меньше материала — ведь пауки сами производят материал для паутины. В итоге он решил укрепить только некоторые нити, но важно, чтобы каждый узел паутины был достижим по укреплённым нитям.
Кроме того, Саймон планирует проводить время на одной из укреплённых нитей и хочет, чтобы эта нить была длинной. Поэтому при расчёте общей длины всех укреплённых нитей длина самой длинной укреплённой нити будет вычитаться из общей суммы. Помогите Саймону выбрать нити для укрепления, чтобы минимизировать общую длину при этих условиях.
Входные данные
Входные данные содержат описания нескольких паутин. Первая строка каждого описания содержит два числа: число 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" вместо стоимости.