eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Минимальный каркас

Минимальный каркас

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

В связном графе найдите остовное дерево минимального веса.

Входные данные

Первая строка содержит два натуральных числа n и m (1n20000, 0m100000) - количество вершин и рёбер графа соответственно. Следующие m строк содержат описания рёбер по одному в строке. Ребро номер i описывается тремя натуральными числами b[i], e[i] и w[i] (1b[i], e[i]n, 0w[i]100000) - номера концов ребра и его вес соответственно.

Граф является связным.

Выходные данные

Выведите единственное целое число - вес минимального остовного дерева.

Пример

Входные данные #1
4 4
1 2 1
2 3 2
3 4 5
4 1 4
Выходные данные #1
7