Спасибо, что помогаете Хайди! Сегодня второе апреля, но ее снова вызвала Дженни. Шутка еще не закончилась...
Тем временем Хайди решила, что больше не доверяет своим друзьям. Во всяком случае, не слишком доверяет. Ее относительное отсутствие доверия проявляется следующим образом: в то время как ранее ей не пришлось бы посещать одного и того же человека дважды, теперь она может быть уверена лишь в том, что ее не заставят посетить одного и того же друга более чем k раз.
В случае с Дженни первое её посещение в начале учитывается. Ситуация с простой версией задачи соответствует случаю для k = 1.
Это не так плохо, как кажется, поскольку один билет на маршрут между двумя друзьями позволяет Хайди путешествовать между этой парой друзей целый день (в обоих направлениях). Другими словами, как только она платит за путешествие между парой друзей, все дальнейшие путешествия между этой парой бесплатны.
Каково максимальная сумма денег, которые Хайди может потратить на путешествия между друзьями?
В первой строке следует два целых числа n и k (
, 1 ≤ k ≤ 105) — количество друзей и максимальное количество посещений каждого из друзей.
В следующих n - 1 строках следует по три целых числа u, v и c (0 ≤ u, v ≤ n - 1, 1 ≤ c ≤ 104), означающих, что u и v являются друзьями и стоимость путешествия между ними равна c.
Гарантируется, что дружеские связи из входных данных формируют дерево.
Выведите одно целое число — максимальную сумму денег, которые Хайди может потратить на путешествия между друзьями.
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. Обратите внимание, что ни один друг не посещается более чем 3 раза.
