Maximal Shopping
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 0.4s, Memory Limit: 64MiB
Елeонора е кифла. Всеки път, когато отвoрят нов мол, за нея е малък празник. Тя е толкова въодушевена, че отива да го разгледа още на първия ден от отварянето му.

Явно Ели не е единствената кифла в София, тъй като освен нея там има и огромно количество други хора. Тя е отбелязала нейните N любими марки, които имат представителство в новия мол, като е разгледала и какви коридори има в него между двойки от тях и колко хора се движат по всеки от тях. Колкото повече хора – толкова по-трудно тя се придвижва с всичките чанти, които е напазарувала.

Ели е решила да изпълни съставеният от нея план "Maximal Shopping There" и да намери такова подмножество от пътеки, че да може да стигне от всеки магазин до всеки друг (използвайки един или повече коридори) като в същото време сумарно хората по тях са възможно най-малко.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M – съответно броят магазини и броят коридори между двойки от тях. Следващите M реда ще съдържат по три числа Ai Bi Pi, указващи, че между магазините с индекси Ai и Bi има коридор, по който минават Pi човека. Възможно е да съществуват по повече от един коридор между два магазина, а дори и коридор от магазин до самия себе си (футуристична архитектура). Все пак молът е така конструиран, че винаги да има набор от коридори, които позволяват да се стигне от всеки магазин до всеки друг. Разбира се, както хората, така и Ели, могат да се движат и в двете посоки по коридорите.
Изход
На стандартния изход изведете едно цяло число – броя хора в оптималното подмножество от коридори, което Ели може да избере.
Ограничения
  • 1 ≤ N ≤ 20,000
  • 1 ≤ M ≤ 200,000
  • 1 ≤ Pi ≤ 20,000
  • 1 ≤ Ai, BiN
Примерен Вход Примерен Изход
9 12 1 4 3 4 2 3 1 2 3 1 3 10 2 5 2 2 6 1 3 5 3 5 8 10 5 7 7 5 6 2 6 9 4 9 8 1 24
Мрън!