Minimum Roads Removal for a Simple City Layout

You are given a city represented as a graph with n intersections and m bidirectional roads. Each road connects two intersections and has an associated travel time. Your task is to determine the minimum number of roads that should be removed so that the remaining road network forms a simple structure. In this problem, the simple structure is achieved when the network becomes a spanning tree (or, more generally, a structure with no redundant roads).

Insight: If the city is originally connected, a spanning tree will contain exactly \(n-1\) roads. Thus, the number of roads to remove is given by:

[ \text{Answer} = m - (n-1) ]

However, if the network is not initially connected, you should build a minimum spanning forest and remove all the extra roads not used in the forest. In our approach, we compute the minimum spanning forest using a union-find structure and a greedy selection of roads based on their travel time.

inputFormat

The input is given via standard input (stdin) and has the following format:

n m
u1 v1 t1
u2 v2 t2
... 
um vm tm

where:

• n is the number of intersections.
• m is the number of roads.
• Each of the next m lines contains three integers u, v, t representing a road between intersections u and v with travel time t.

outputFormat

The output should be a single integer printed to standard output (stdout) – the minimum number of roads that must be removed.

## sample

5 5
1 2 10
2 3 15
3 4 10
4 5 5
3 5 3

1