Minimum Roads Removal for an Acyclic Network

You are given a network of cities connected by roads. Each road has a unique length. The network is represented as an undirected weighted graph with n cities (nodes) and m roads (edges). Your task is to remove the minimum number of roads such that the remaining road network is acyclic, i.e. it forms a tree (or a forest if the graph is disconnected).

Recall that a tree with n nodes must have exactly n - 1 edges. In this problem, you are allowed to remove roads that create cycles in order to meet this requirement. Formally, if you have a cycle, you need to remove at least one edge from that cycle. The goal is to minimize the total number of edges removed.

The problem can be solved using a modified union-find algorithm where edges are processed in descending order of their weights. This strategy guarantees that the most valuable roads (in terms of weight) are kept, and only those that introduce cycles are removed.

The key steps are:

• Sort the edges in descending order by weight.
• Iterate over the sorted list and, for each edge, use a union-find (disjoint set) data structure to determine if adding that edge would form a cycle.
• If it forms a cycle, increase the counter for roads that must be removed; otherwise, merge the sets.

The final answer is the number of roads removed to achieve an acyclic network.

Note: All formulas, such as the property of a tree (n - 1 edges for n nodes), are represented in LaTeX format when necessary, e.g. \(n-1\).

inputFormat

The input is read from stdin and is in the following format:

<n> <m>
<u1> <v1> <w1>
<u2> <v2> <w2>
... 
<um> <vm> <wm>

Here:

• n is the number of cities.
• m is the number of roads.
• Each of the next m lines contains three space-separated integers: u, v (the cities connected by the road), and w (the length of the road).

outputFormat

Print a single integer to stdout: the minimum number of roads to remove so that the network becomes acyclic (i.e. a tree or forest).

## sample

5 6
1 2 6
1 3 2
2 4 5
2 5 7
3 4 3
3 5 4

2