e-olymp
Задачи

Граффити

Граффити

Задан взвешенный неориентированный граф с n вершинами и m ребрами. Граф не содержит петель и может быть нарисован на плоскости. Нурлашко восстановил граф на плоскости и построил следующий граф: грани (области) на плоскости стали вершинами, а ребрами между ними стали ребра, общие к этим граням. Например, если 2 грани имели общее ребро в исходном графе, то следует добавить ребро между гранями в новом графе. Теперь Нурлашко хочет найти минимальное остовное дерево нового графа. Минимальное остовное дерево - это связное дерево с n вершинами с минимальной суммой ребер в дереве.

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

Первая строка содержит 2 целых числа n и m (3n1000000, 0m200000). Каждая из следующих m строк содержит 3 целых числа: u, v, c (1u, vn, uv, -106c106), где u и v - вершины, c - вес соединяющего их ребра.

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
3 3
1 2 1
2 3 1
1 3 1
Выходные данные #1
1
Источник 2019 Fall KBTU OPEN, Задача G