Задачі
Мінімальний каркас
Мінімальний каркас
Потрібно знайти у зв'язному графі остовне дерево мінімальної ваги.
Вхідні дані
Перший рядок містить два натуральних числа n та m (1 ≤ n ≤ 20000, 0 ≤ m ≤ 100000) - кількість вершин та ребер графа відповідно. Наступні m рядків містять описи ребер по одному у рядку. Ребро номер i описується трьома натуральними числами bi
, ei
та wi
(1 ≤ bi
, ei
≤ n, 0 ≤ wi
≤ 100000) - номери кінців ребра та його вага відповідно.
Граф є зв'язним.
Вихідні дані
Виведіть єдине ціле число - вагу мінімального остовного дерева.
Вхідні дані #1
4 4 1 2 1 2 3 2 3 4 5 4 1 4
Вихідні дані #1
7