Олимпиадный тренинг

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


Задача

Темы:
Президент Берляндии обратился к вам за помощью! В его стране есть 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




time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w646
Комментарий учителя