К 3031 году ICPC стал настолько популярен, что пришлось построить целый новый город, чтобы разместить все команды финала мира. Город красиво спроектирован, имеет дорожную сеть. К сожалению, при составлении бюджета градостроители забыли учесть стоимость знаков ограничения скорости. Они попросили Вас помочь им определить минимальные дополнительные средства, которые им понадобятся. Дорожная сеть ICPC состоит из дорог, каждая из которых соединяет два перекрестка. Каждая дорога является двусторонней, и ей уже присвоено ограничение скорости, действительное для обоих направлений. В целях экономии использовалось минимально возможное количество дорог. Другими словами, существует ровно один маршрут от любого перекрестка до любого другого перекрестка. Знаки ограничения скорости необходимо устанавливать во всех местах, где ограничение скорости может измениться для любого водителя, следующего по любому маршруту. Точнее, если существует перекресток, на котором пересекаются хотя бы две дороги с разными ограничениями скорости, то на всех дорогах, идущих от этого перекрестка, на этом перекрестке должен быть установлен знак ограничения скорости. Обратите внимание, что на некоторых дорогах могут потребоваться два знака ограничения скорости, по одному на каждом конце. Установка одного знака ограничения скорости стоит $c$ долларов. Также возможно повысить безопасность и качество любой дороги, увеличив на ней ограничение скорости, что, в свою очередь, может уменьшить количество необходимых знаков ограничения скорости. Увеличение предельной скорости на одной дороге на $x$ км/ч (в обоих направлениях) стоит $x$ долларов. Во избежание жалоб городской совет не разрешает снижать ни один из уже установленных ограничений скорости. Рисунок B.1 представляет ситуацию как для входных данных 1, так и для входных данных 2. \includegraphics{https://static.eolymp.com/content/l3/l39i9j33r539t7s9jecscs282k.gif} \InputFile В первой строке записаны два целых числа $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)$ --- текущее ограничение скорости на этой дороге в километрах в час. \OutputFile Выведите минимальную стоимость модернизации дорог и установки знаков ограничения скорости так, чтобы план города удовлетворял всем приведенным выше правилам.