410217: GYM103985 C Королевские вопросы

C. Королевские вопросыограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

В одном средневековом королевстве бушует экономический кризис. Надои молока падают, экономические показатели каждый день пробивают новое дно, деньги из казны пропадают в неизвестном направлении. Чтобы исправить положение, король Карл Солнцеликий принял решение женить своих n сыновей-принцев на невестах с, по возможности, как можно б'{о}льшим приданым.

В поисках кандидаток король отправил гонцов в соседние королевства, в результате чего ко двору прибыли делегации с m незамужними принцессами. Принимая гостей, Карл узнал, что приданое i-й принцессы составляет w_i золотых монет.

Хотя дело и происходит в средневековье, в обществе уже широко распространены прогрессивные представления, в соответствии с которыми никто не может заставить принцессу выйти замуж за принца, который ей не по нраву. Поэтому каждой принцессе была предоставлена возможность выбрать двух принцев, за каждого из которых она готова выйти замуж. Принцам повезло меньше, они в вопросе выбора невесты будут повиноваться воле своего отца.

Зная размер приданого и предпочтения каждой принцессы, Карл хочет сыграть свадьбы таким образом, чтобы суммарное приданое невест всех его сыновей было как можно больше. При этом женить всех принцев или выдавать всех принцесс замуж не обязательно. Каждый принц может жениться не более чем на одной принцессе, и наоборот каждая принцесса может быть выдана не более чем за одного принца.

Помогите королю организовать женитьбу своих сыновей наиболее выгодным для казны способом.

Входные данные

В первой строке находятся два целых числа n, m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000) — количество принцев и количество принцесс соответственно.

В каждой из последующих m строк находится по три целых числа a_i, b_i, w_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 1 ≤ w_i ≤ 10 000) — номера принцев, за которых готова выйти замуж i-я принцесса и размер её приданого.

Выходные данные

Выведите единственное целое число — максимальное количество золотых монет, которое может получить король, сыграв нужные свадьбы.

ПримерыВходные данные

2 3
1 2 5
1 2 1
2 1 10

Выходные данные

15

Входные данные

3 2
1 2 10
3 2 20

Выходные данные

30