Repairs
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 0.1s, Memory Limit: 64MiB
Ели обича общинските избори. Макар и само два месеца на всеки няколко години, те са времето, когато общината почва да чисти улиците, прави ремонти, сменя кошчетата за боклук и т.н. Сега отново идват избори, но този път всичко е различно! Както може и да знаете (от задачата Bribes), Ели беше избрана на предходните избори. В ярък контраст с други общински управници, тя няма да инвестира парите само за да отбие номера. Тя е решила да асфалтира улиците, които имат най-голяма нужда от ремонт.

В града, където управлява тя, има N кръстовища и M двупосочни улици, за всяка от които тя е определила колко "развалена" е, тоест до каква степен улицата се нуждае от ремонт. За съжаление, докато се ремонтира една улица, по нея не могат да преминават автомобили, което би могло да доведе до неудобство за гражданите. Също така, тъй като времето е кратко, всички улици, избрани за ремонтиране, ще бъдат ремонтирани едновременно. Помогнете ѝ да избере тези от тях, които биха дали най-голяма печалба на населението (тоест имат най-голяма сумарна нужда от ремонт), като в същото време остане поне един път от всяко кръстовище до всяко друго.
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и M – съответно броя върхове и ребра в графа. Всеки от следващите M реда ще съдържа по три цели числа – Ai Bi Di, указващи, че има двупосочна улица между кръстовища Ai и Bi, чиято нужда от ремонт е Di.
Изход
На единствен ред на стандартния изход изведете едно цяло число – каква най-голяма сумарна печалба може да има от ремонта за населението. Ако дори без да се ремонтират улици има двойка кръстовища, които са недостижими едно от друго, вместо това изведете -1.
Ограничения
  • 1 ≤ N ≤ 10,000
  • 1 ≤ M ≤ 100,000
  • 1 ≤ AiBiN
  • 1 ≤ Di ≤ 100,000
Примерен Вход Примерен Изход
4 5 1 2 4 1 3 3 2 4 6 1 4 3 3 4 1 9
3 1 1 2 42 -1
В първия пример най-добре е да ремонтираме улиците със стойности 6 и 3.
Мрън!