Kingdom#673
In the fairy kingdom, there are cities. Some pairs of cities are connected by roads, and the same pair of cities can be connected by several roads. Outside the cities, the roads do not intersect. You can travel on each road in any direction. Help the King determine how many additional roads need to be built in the kingdom, so that His Majesty will be able to travel on all roads without traversing any of them twice. Usually (see the example), he must visit each city. The King's journey should start and end in the same city.
The first number entered is the number of cities in the kingdom, (1 \leq N \leq 100), followed by the number of city pairs, (1 \leq K \leq 10000). Then, in groups of 3 numbers, you are given the numbers of two cities and the number of roads connecting them (all the numbers do not exceed ). All numbers are separated by spaces.
Output the smallest possible number of roads that need to be added.
Example 1