Maximum Toll Booths Placement

You are given a city with n intersections and m roads. Each road is represented by three integers u, v, and t where the road connects intersections u and v with a toll value t (the toll value does not affect the placement decision).

Your task is to install as many toll booths as possible on the roads such that no two selected roads share a common intersection. In other words, you need to choose a subset of the roads that forms a matching in the graph. The answer is the maximum number of toll booths (i.e. roads) you can select.

Note: The solution should process the input from standard input (stdin) and print the result to standard output (stdout). If there are no roads, the answer is 0.

Mathematical Formulation:

Given an undirected graph \(G=(V,E)\) with \(|V| = n\) and \(|E| = m\), find the maximum matching \(M \subseteq E\) such that for any two edges \(e_1, e_2 \in M\), \(e_1 \cap e_2 = \emptyset\). Output \(|M|\).

inputFormat

The first line contains two integers n and m separated by a space, representing the number of intersections and the number of roads, respectively.

Each of the next m lines contains three integers u, v, and t, where u and v (1-indexed) are the intersections connected by the road and t is the toll value (which is not used in the computation).

outputFormat

Output a single integer: the maximum number of toll booths (i.e. roads) that can be chosen without any two of them sharing an intersection.

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

2