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