Графіті#9413
Дано зважений неорієнтований граф з вершинами та ребрами. Граф не містить петель і може бути намальований на площині. Нурлашко відновив граф на площині та побудував новий граф: грані (області) на площині стали вершинами, а ребрами між ними стали ребра, спільні для цих граней. Наприклад, якщо грані мали спільне ребро в початковому графі, то слід додати ребро між цими гранями в новому графі. Тепер Нурлашко хоче знайти мінімальне остовне дерево нового графа. Мінімальне остовне дерево - це зв'язне дерево з вершинами з мінімальною сумою ваг ребер у дереві.
Перший рядок містить цілі числа і (3 \leq n \leq 1000000, 0 \leq m \leq 200000). Кожен з наступних рядків містить цілі числа: , , (1 \leq u, v \leq n, u \neq v, -10^6 \leq c \leq 10^6), де і - вершини, - вага з'єднуючого їх ребра.
Виведіть одне ціле число - вагу мінімального остовного дерева.
Приклад 1