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

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

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

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

Определить вес минимального остовного дерева для неориентированного взвешенного связного графа.

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

В первой строке находится количество вершин n и рёбер m~(1 \le n \le 100, 1 \le m \le 6000) в графе. Каждая из следующих m строк содержит тройку чисел a, b, c, где a и b — номера вершин, соединённых ребром, а c — вес ребра (натуральное число, не превышающее 30000).

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

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

Пример

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