Обработка математики: 100%
 

printЗадачи командного чемпионата

printC. Строительство дорог

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Король Флатландии решил направить свою страну по пути научно-технического прогресса и повелел построить K железных дорог таким образом, чтобы из любого города страны можно было проехать до любого другого по железной дороге прямо или с пересадками через другие города. Железнодорожные компании, заинтересованные в финансировании, предложили министру транспорта откат в случае принятия их предложений. Хитрый министр решил построить дороги таким образом, чтобы не только обеспечить выполнение приказа короля, но и получить максимальный доход.
В первой строке ввода содержатся три целых числа, разделенных пробелами – количество городов в стране N (1 < N  30000), число предложений от компаний M (N-1  M  105) и количество дорог K (N-1  K  M). Далее следует M строк, содержащих по три целых числа – номера городов ai и bi (1  ai < bi  N), между которыми предлагается построить дорогу, и величина отката ci (0  ci  109). Пары городов в списке предложений не повторяются.
Вывести одно целое число – максимальный доход министра. Если выполнить приказ короля невозможно, вывести число -1.

Пример ввода

4 6 5
1 2 200
1 3 100
1 4 150
2 3 90
2 4 180
3 4 120

Пример вывода

750
loading