eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Тренировки

Тренировки

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Мирко и Славко настойчиво тренируются перед ежегодным веломарафоном для тандемов, который пройдет в Хорватии. Им нужно выбрать маршрут для тренировок.

В стране N городов и M дорог. Каждая дорога соединяет два города, и по ней можно ехать в обеих направлениях. Ровно N-1 из этих дорог мощеные, а остальные дороги - немощеные тропы. К счастью, сеть дорог устроено так, что произвольную пару городов соединяет путь, состоящий только из мощеных дорог. Другими словами, N городов и N-1 мощеных дорог образуют структуру дерева.

Дополнительно известно, что в каждом городе оканчивается не более 10 дорог.

Тренировочный маршрут начинается в некотором городе, проходит по некоторым дорогам и завершается в том же городе, где начался. Мирко и Славко любят посещать новые города, поэтому они ввели правило: никогда не проезжать через одно и то же место, а также по одной и той же дороге дважды. Тренировочный маршрут может начинаться в произвольном городе и не обязательно проходить по всем городам.

В тандеме ехать на заднем сидении легче, так как велосипедист защищен от ветра партнером, сидящим спереди. Поэтому Мирко и Славко меняются местами в каждом городе. Чтобы получить одинаковую нагрузку на тренировке, они должны выбрать маршрут с парным количеством дорог.

Противники Мирка и Славка решили заблокировать некоторые тропинки, чтобы было невозможно построить тренировочный маршрут, удовлетворяющий перечисленным требованиям. Для каждой тропинки известно цену её блокировки (положительное целое число). Мощеные дороги блокировать нельзя.

Напишите программу, которая по описанию сети городов и дорог находит минимальную общую стоимость, нужную для блокирования дорог таким образом, чтобы не существовало тренировочного маршрута, удовлетворяющего перечисленным требованиям.

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

Первая строка входных данных содержит два целых числа N и M, задающих количество городов и общее количество дорог. (2 ≤ N ≤ 1000, N - 1 ≤ M ≤ 5000).

Каждая из последующих M строк содержит три целых числа A, B и C (1 ≤ A, B ≤ N, 0 ≤ C ≤ 10000), которые описывают одну дорогу. Числа A и B различны и определяют города, напрямую соединенные дорогой. Если C = 0 - дорога мощеная; иначе - это тропинка, и число C задает цену блокировки дороги.

В каждом городе заканчивается не более 10 дорог. Два города соединены напрямую не более, чем одной дорогой.

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

Выходные данные должны содержать одне целое число - наименьшую общую стоимость, описанную выше.

Пример

Входные данные #1
5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1
Выходные данные #1
5
Источник IOI-2007, День 2