Вартість обмеження швидкості

До 3031 року ICPC став настільки популярним, що виникла потреба побудувати нове місто для розміщення всіх команд, які беруть участь у фіналі світу. Це місто має добре сплановану дорожню мережу. На жаль, при складанні бюджету містобудівники забули врахувати витрати на знаки обмеження швидкості. Вони звернулися до вас за допомогою, щоб визначити мінімальні додаткові кошти, які їм знадобляться.

Дорожня мережа ICPC складається з доріг, кожна з яких з'єднує два перехрестя. Кожна дорога є двосторонньою і вже має встановлене обмеження швидкості, яке діє в обох напрямках. Для економії була використана мінімально можлива кількість доріг. Іншими словами, існує рівно один маршрут від будь-якого перехрестя до будь-якого іншого.

Знаки обмеження швидкості потрібно встановлювати у всіх місцях, де обмеження швидкості може змінитися для будь-якого водія, що рухається будь-яким маршрутом. Тобто, якщо існує перехрестя, на якому перетинаються принаймні дві дороги з різними обмеженнями швидкості, то на всіх дорогах, що виходять з цього перехрестя, має бути встановлений знак обмеження швидкості. Зверніть увагу, що на деяких дорогах можуть знадобитися два знаки обмеження швидкості, по одному на кожному кінці.

Встановлення одного знака обмеження швидкості коштує $c$ доларів. Також можна підвищити безпеку та якість будь-якої дороги, збільшивши на ній обмеження швидкості, що може зменшити кількість необхідних знаків обмеження швидкості. Збільшення граничної швидкості на одній дорозі на $x$ км/год (в обох напрямках) коштує $x$ доларів. Щоб уникнути скарг, міська рада не дозволяє знижувати жодне з уже встановлених обмежень швидкості.

Рисунок B.1 ілюструє ситуацію як для вхідних даних 1, так і для вхідних даних 2.

Вхідні дані

У першому рядку записані два цілі числа $n$ і $c$, де $n(1\le n\le 20000)$ — кількість перехресть, а $c(1\le c\le 10^5)$ — вартість встановлення одного знака. У кожному з наступних $n-1$ рядків записано по три цілі числа $u,v$ і $s$, де $u$ і $v(1\le u,v\le n,u\ne v)$ — перехрестя на кінцях дороги, а $s(1\le s\le 10^5)$ — поточне обмеження швидкості на цій дорозі в кілометрах на годину.

Вихідні дані

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

Приклади