Описание

Ограничение по времени: 1000 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Мишина машина (В', В)

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

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

Формат входных данных
первой строке содержатся два целых числа n и m количество городов и дорог соедин¤ющий
города в стране соответственно (1 <= n <= 105 , 0<= m <= 105)
 
В следующих m строках содержится по три целых числа, разделенных пробелами номера, -  городов, соединенных очередной дорогой и количество ям на этой дороге соответственно. Количество
ям на каждой дороге неотрицательное число не превосходящее 106
 
Гарантируетс¤ что никакая дорога не соединяет город с самим собой и что нет двух дорог соединяющих одинаковые пары городов.
Вершины нумеруются с единицы.
 
Формат выходных данных
Выведите одно число максимальное количество монет которое Миша сможет получить.

Ввод Вывод
4 4
1 2 1
2 3 1
1 4 1
4 3 0
3
4 2
1 3 5
2 4 4
5

Замечание
Все дороги двусторонние; проехав в любую сторону по дороге, Миша посещает все ямы на этой дороге. Обратите внимание, что между некоторыми парами городов может не существовать пути по имеющимся дорогам.


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: