Рабочее место участника

Король Флатландии решил направить свою страну по пути научно-технического прогресса и повелел построить `K` железных дорог таким образом, чтобы из любого города страны можно было проехать до любого другого по железной дороге прямо или с пересадками через другие города. Железнодорожные компании, заинтересованные в финансировании, предложили министру транспорта откат в случае принятия их предложений. Хитрый министр решил построить дороги таким образом, чтобы не только обеспечить выполнение приказа короля, но и получить максимальный доход.

В первой строке ввода содержатся три целых числа, разделенных пробелами – количество городов в стране `N` (`1\ <\ N\ ≤\ 30000`), число предложений от компаний `M` (`N-1\ ≤\ M\ ≤\ 10^5`) и количество дорог `K` (`N-1\ ≤\ K\ ≤\ M`). Далее следует `M` строк, содержащих по три целых числа – номера городов `a_i` и `b_i` (`1\ ≤\ a_i\ <\ b_i\ ≤\ N`), между которыми предлагается построить дорогу, и величина отката `c_i` (`0\ ≤\ c_i\ ≤\ 10^9`). Пары городов в списке предложений не повторяются.

Вывести одно целое число – максимальный доход министра. Если выполнить приказ короля невозможно, вывести число `-1`.

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

750