2019 Fall KBTU OPEN


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.


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


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

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 3
1 2 1
2 3 1
1 3 1
Output example #1
Source 2019 Fall KBTU OPEN, Problem G