Тренування

Мірко і Славко наполегливо тренуються перед щорічним веломарафоном для тандемів, який пройде в Хорватії. Їм потрібно обрати маршрут для тренувань.

У країні $N$ міст і $M$ доріг. Кожна дорога з'єднує два міста, і по ній можна їхати в обох напрямках. Рівно N-1 з цих доріг мощені, решта доріг — незамощені стежки. Мережа доріг влаштована так, що кожну пару міст з'єднує шлях, який складається лише з мощених доріг. Іншими словами, $N$ міст і N-1 мощених доріг утворюють дерево.

Додатково, кожне місто є кінцем не більше ніж $10$ доріг.

Тренувальний маршрут починається в деякому місті, проходить по деяких дорогах і закінчується в тому ж місті, де почався. Мірко і Славко люблять відвідувати нові міста, тому встановили правило: ніколи не проїжджати через одне й те саме місто і не їхати однією й тією самою дорогою двічі протягом одного маршруту. Маршрут може починатись у будь-якому місті і не обов'язково проходити через усі міста.

На тандемі їхати на задньому сидінні легше, бо партнер спереду захищає велосипедиста від вітру. Тому Мірко і Славко міняються місцями в кожному місті. Щоб тренування було однаковим для обох, маршрут має містити парну кількість доріг.

Суперники вирішили заблокувати деякі з незамощених стежок, щоб не можна було побудувати тренувальний маршрут, що задовольняє описаним вимогам. Для кожної стежки відома вартість її блокування (додатне ціле число). Мощені дороги блокувати не можна.

Напишіть програму, яка за описом міст та доріг визначає мінімальну сумарну вартість блокування, щоб не існувало жодного тренувального маршруту, що задовольняє вказаним вимогам.