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

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

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

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

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