Представьте, как должна выглядеть яблоня в двоичном компьютерном мире. Вы правы, она выглядит как двоичное дерево, то есть любая ветка двоичной яблони может ветвиться в точности на две новые ветки. Занумеруем целыми числами корень двоичной яблони, точки ветвления и верхушки верхних ветвей. Пусть корень дерева всегда имеет номер 1, а все числа, используемые при нумерации, лежат в пределах от 1 до N, где N — общее число пронумерованных точек. На рисунке ниже приведён пример нумерации дерева с четырьмя ветвями. N здесь равно 5.

Как вы понимаете, не очень удобно собирать яблоки с яблони, у которой много ветвей. Вот почему некоторые ветви следует удалить из дерева. Но вы также заинтересованы в удалении ветвей, которое приведёт к минимальной потере яблок. Известно количество яблок на каждой из ветвей, а также количество ветвей, которые нужно сохранить. Ваша задача — определить, сколько яблок можно оставить на яблоне, удалив лишние ветви.

В первой строке даны числа N и Q (2 ≤ N ≤ 100; 1 ≤ Q ≤ N − 1). N обозначает количество пронумерованных точек в дереве, а Q — количество ветвей, которые нужно сохранить. Следующие N − 1 строк содержат описание ветвей. Описание каждой ветви состоит из трёх чисел, разделённых пробелом. Первые два из них определяют конечные точки ветви, третье — число яблок на данной ветви. Вы можете считать, что любая ветвь содержит не более 30000 яблок.

Выведите единственное число — максимальное количество яблок, которое можно сохранить. Не забудьте сохранить корень яблони ;-)