Kingdom

In the fairy kingdom N cities. Some pairs of cities connected by roads, with one and that same pair of cities can connect several roads. Outside the cities the roads do not intersect. On every road you can go in any direction. Help the King to determine skoloi still need to build roads in the kingdom, that His Majesty was able to travel on all roads, not prooezzhaya twice on any of them. Usually (see example), he has to visit each city. Travel King should nachinatsya and ends with in the same city.

Input

You enter the first number in the kingdom cites N (1 ≤ N≤100) and the number of city pairs K (1≤K≤10000). Then, in groups of 3 to the number you enter the number of towns and number of roads connecting them (all the numbers do not exceed 100). All numbers rozdeleny space.

Output

You draw the smallest possible number of roads.