Граффити
Граффити
Задан взвешенный неориентированный граф с n вершинами и m ребрами. Граф не содержит петель и может быть нарисован на плоскости. Нурлашко восстановил граф на плоскости и построил следующий граф: грани (области) на плоскости стали вершинами, а ребрами между ними стали ребра, общие к этим граням. Например, если 2 грани имели общее ребро в исходном графе, то следует добавить ребро между гранями в новом графе. Теперь Нурлашко хочет найти минимальное остовное дерево нового графа. Минимальное остовное дерево - это связное дерево с n вершинами с минимальной суммой ребер в дереве.
Giriş verilənləri
Первая строка содержит 2 целых числа n и m (3 ≤ n ≤ 1000000, 0 ≤ m ≤ 200000). Каждая из следующих m строк содержит 3 целых числа: u, v, c (1 ≤ u, v ≤ n, u ≠ v, -10^6
≤ c ≤ 10^6
), где u и v - вершины, c - вес соединяющего их ребра.
Çıxış verilənləri
Выведите одно целое число - вес минимального остовного дерева.
Nümunə
3 3 1 2 1 2 3 1 1 3 1
1