Королівство#673
У казковому королівстві міст. Деякі пари міст з'єднано дорогами, причому одну і ту саму пару міст можуть з'єднувати декілька доріг. Поза межами міст дороги не перетинаються. По кожній дорозі можна їхати в будь-якому напрямку. Допоможіть королю визначити, скільки ще доріг потрібно побудувати у королівстві, щоб Його Величність зміг зробити подорож по всіх дорогах, не проїзджаючи двічі по жодній з них. Зазвичай (див. приклад), він має бажання відвідати кожне місто. Подорож короля повинна починатися і закінчуватися в одному і тому ж місті.
Спочатку вводиться кількість міст у королівстві (1 \leq N \leq 100) і кількість пар міст (1 \leq K \leq 10000). Потім у групах по 3 числа вводяться номери міст і кількість доріг, що їх з'єднують (усі числа не перевищують ). Усі числа розділені пропуском.
Виведіть мінімально можливу кількість доріг, які потрібно додати.
Приклад 1