Мірко і Славко наполегливо тренуються перед щорічним веломарафоном для тандемів, який пройде в Хорватії. Їм потрібно обрати маршрут для тренувань. У країні \textbf{N} міст i \textbf{M} доріг. Кожна дорога з'єднує два міста, і по ній можна їхати в обох напрямках. Рівно \textbf{N-1} з цих доріг є мощениеми, а решта доріг - незамощені стежки. На щастя, мережу доріг влаштовано так, що довільну пару міст з'єднує шлях, що складається лише з мощених доріг. Іншими словами, \textbf{N} міст і \textbf{N-1} мощених доріг утворюють структуру дерева. Додатково відомо, що в кожному місті закінчується не більше \textbf{10} доріг. Тренувальний маршрут починається в деякому місті, проходить по деяких дорогах і закінчується в тому ж місті, де почався. Мірко і Славко люблять відвідувати нові міста, так що вони ввели правило: ніколи не проїзджати через одне й те саме місце, а також по одній і тій самій дорозі двічі. Тренувальний маршрут може починатись у довільному місті і не зобов'язаний проходити через усі міста. У тандемі їхати на задньому сидінні легше, тому що велосипедист захищений від вітру партнером, що сидить спереду. Із-за цього Мірко і Славко міняються місцями в кожному місті. Щоб отримати однакове навантаження на ренуванні, вони повинні обрати маршрут з парною кількістю доріг. Суперники Мірка і Славка вирішили заблокувати деякі стежки, щоб було не можливо побудувати тренувальний маршрут, що задовольняє перерахованим вимогам. Для кожної стежки відомо ціну її блокування (додатне ціле число). Мощені дороги блокувати не можна. Напишіть програму, яка за описом мережі міст та доріг знаходить найменшу загальну вартість, що потрібну для блокування доріг таким чином, щоб не існувало тренувального маршруту, що задовольняє перерахованим вимогам. \InputFile Перший рядок вхідних даних містить два цілих числа \textbf{N} і \textbf{M}, що задають кількість міст і загальну кількість доріг. (\textbf{2 ≤ N ≤ 1000}, \textbf{N - 1 ≤ M ≤ 5000}). Кожен з наступних \textbf{M} рядків містить три цілих числа \textbf{A}, \textbf{B} і \textbf{C} (\textbf{1 ≤ A}, \textbf{B ≤ N}, \textbf{0 ≤ C ≤ 10000}), що описують одну дорогу. Числа \textbf{A} і \textbf{B} є різними і визначають міста, що напряму з'єднані дорогою. Якщо \textbf{C = 0} - дорога є мощеною; інакше - це стежка, і число \textbf{C} задає ціну блокування дороги. У кожному місті закінчується не більше \textbf{10} доріг. Два міста з'єднані напряму не більше однією дорогою. \OutputFile Вихідні дані мають містити одне ціле число - найменшу загальну вартість, описану вище.