Graphity#9413
You are given weighted undirected graph with vertices and edges. Graph doesn't contain loops and can be drawn on the plane. NurlashKO has restored the graph on the plane, and built 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 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 vertices with minimal sum of the edges in the tree.
In the first line you are given integers and (3 \leq n \leq 1000000, 0 \leq m \leq 200000). Next lines contain integers each: , , (1 \leq u, v \leq n, u \neq v, -10^6 \leq c \leq 10^6), where and are the vertices, and is the weight of the edge connecting these vertices.
Print single integer, the total weight of the minimum spanning tree.
Example 1