Описание

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

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

Задача: Дорогие дороги

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

Входные данные:
В первой строке задано два целых числа - n и m (2 <= n <= 300000, n - 1  <= m <= 300000).
В следующих m строках содержатся три числа - u, v и w (1 <= u, v <= n, 0 <= w <= 109) - дорога между городами u и v, стоимость ремонта которой w.

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

(с) Ибрахим Ахмад, 2018


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


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

Ваш ответ:

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


Нет

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