Minimum Sensors

You are given a city with N intersections and M roads. Each road is represented by three integers: u, v, and w (the weight w is provided but not used in the computation). The goal is to determine the minimum number of sensors required to monitor all roads, where a road is considered monitored if at least one of its endpoint intersections is equipped with a sensor.

This problem can be formulated as a vertex cover problem. In graph theory, a vertex cover of a graph \(G = (V, E)\) is a subset \(S \subseteq V\) such that for every edge \((u,v) \in E\), at least one of \(u\) or \(v\) belongs to \(S\). The objective is to minimize \(|S|\). Note that while the vertex cover problem is NP-hard, a simple greedy algorithm is used in this problem and it works well for the given test cases.

inputFormat

The first line of input contains two integers N and M separated by a space.

The next M lines each contain three integers u, v, and w describing a road between intersections u and v with weight w.

If M = 0, then there are no roads.

outputFormat

Output a single integer which is the minimum number of sensors required to monitor all roads.

4 3
1 2 2
2 3 3
3 4 4

2