Задачи
Минимальный каркас
Минимальный каркас
В связном графе найдите остовное дерево минимального веса.
Входные данные
Первая строка содержит два натуральных числа 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