Cycle Elimination with Maximum Removed Weight

You are given an undirected graph with n nodes and m edges. Each edge connecting nodes i and j has an associated weight f(i,j). Your task is to remove some edges such that:

• The resulting graph does not contain any cycles (i.e. it becomes a spanning tree or spanning forest preserving the connectivity of each original connected component).
• The connectivity among nodes is not altered; that is, for any pair of nodes originally connected, they must remain connected after removing the edges.
• The sum of the weights of the removed edges, \(\sum f(i,j)\), is maximized.

Hint: Removing edges with maximum total weight is equivalent to keeping a spanning tree (or spanning forest) with the minimum total weight. If \(W_{total}\) is the sum of weights of all edges and \(W_{tree}\) is the total weight of the minimum spanning tree (or spanning forest), then the answer is \(W_{total} - W_{tree}\).

inputFormat

The first line contains two integers n and m representing the number of nodes and edges, respectively. The following m lines each contain three integers u, v and w, indicating that there is an edge between node u and node v with weight w.

outputFormat

Output a single integer representing the maximum possible sum of weights of the removed edges.

sample

3 3
1 2 3
2 3 4
1 3 1

4