You are given weighted unordered graph with n vertices and m edges. Graph doesn't contain loops and can be drawn on the plane. NurlashKO has restored the graph on the plane, and build the following graph: the faces (regions) on the plane became vertices, and edges between them were the edges, that is common to these faces, e.g. if 2 faces share the edge in initial graph - add the edge between faces in new graph. Now NurlashKO wants to find the minimum spanning tree of the new graph. Minimum spanning tree is a connected tree with n vertices with minimal sum of the edges in the tree.

Input

In the first line you are given 2 integers n and m (3 ≤ n ≤ 1000000, 0 ≤ m ≤ 200000). Next m lines contain 3 integers each: u, v, c (1 ≤ u, v ≤ n, u ≠ v, -106 ≤ c ≤ 106), where u and v are the vertices, and c is the weight of the edge connecting these vertices.

Output

Print single integer, the total weight of the minimum spanning tree.