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

Граффити

Граффити

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
3 3
1 2 1
2 3 1
1 3 1
Вихідні дані #1
1
Джерело 2019 Fall KBTU OPEN, Задача G