Кайману снится необычный сон, будто он попал в странный район города. Этот район можно представить как граф-дерево, где вершины - это перекрестки и ребра - двусторонние дороги, которые соединяют эти перекрестки. Всего перекрестков n и у каждого свой номер от 0 до n-1.
Но не все так плохо в этом сне, ведь на каждой дороге между перекрестками с номерами u и v есть С
u,v пельменей! Кайман очень любит пельмешки, поэтому хочет съесть как можно больше, но есть проблема - если он побывает в каком-либо перекрестке более чем k раз, то на него нападет злой пельменный монстр.
Хоть это и сон, но пельмешки на каждой дороге можно съесть только один раз, хотя ничего не мешает ходить по дорогам по несколько раз. Также Кайман не останавливается на дорогах. То есть, если он начнет переходить от одного перекрестка к другому, то он обязательно пройдет дорогу полностью до следующего перекрестка.
В начале сна Кайман находится на перекрестке с номером 0. Помогите ему определить, какое максимальное количество пельменей он сможет съесть, но так, чтобы на него не напал злой пельменный монстр.
Входные данные:
В первой строке следует два целых числа n и k (3 ≤ n ≤ 10
5; 1 ≤ k ≤ 10
5) — количество перекрестков и максимальное количество посещений каждого из перекрестков.
В следующих n - 1 строках следует по три целых числа u, v и C
u,v (0 ≤ u, v ≤ n - 1; 0 ≤ C
u,v ≤ 10000), означающих, что перекрестки с номерами u и v связаны дорогой, на которой C
u,v пельменей.
Гарантируется, что перекрестки и дороги формируют дерево.
Выходные данные:
Выведите одно целое число - максимальное количество пельменей, которое сможет съесть Кайман.
Примеры:
| Входные данные |
Выходные данные |
9 3
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3 |
15 |
9 5
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3 |
17 |
11 6
1 0 7932
2 1 1952
3 2 2227
4 0 9112
5 4 6067
6 0 6786
7 6 3883
8 4 7137
9 1 2796
10 5 6200 |
54092 |
Пояснение:
В первом примере нужно посетить перекрестки в следующем порядке: 0, 1, 5, 1, 3, 1, 0, 2, 6, 2, 7, 2, 8. Тогда он съест суммарно 1+2+2+1+3+3+3 = 15 пельменей.
Обратите внимание, что ни один перекресток не посещается более чем 3 раза.