C. Строительство дорог
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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