У казковому королевстві N міст. Деякі пари міст з’єднано дорогами, причому одну і ту саму пару міст можуть з’єднувати декілька доріг. Зовні міст дороги не перетинаються. По кожній дорозі можна їхати в будь-якому напрямку. Допоможіть королю визначити, скільки ще доріг потрібно побудувати у королівстві, щоб Його Величність зміг зробити подорож по всіх дорогах, не проїзджаючи двічі по жодній з них. Звичайно (див приклад нижче), він має бажання відвідати кожне місто. Подорож короля повинна починатись і закінчуватись в одному і тому самому місті.

Вхідні дані

Ви вводите спочатку кількість міст у королівстві N(1 ≤ N ≤ 100) і кількість пар міст К(1 ≤ K ≤ 10000). Потім в К групах по 3 числа ви вводите номери міст і кількості доріг, що їх з'єднують (всі числа не перевищують 100). Всі числа розділені пропуском.

Вихідні дані

Ви виводите мінімально можливу кількість доріг.