Задача H. Созвездие Краба ≡

Условие

Недавно учёные обнаружили необычные связи между некоторыми звёздами в созвездии Краба. Задаваемый этими связями граф представляет собой дерево из n вершин. Каждая связь характеризуется мощностью — вещественным числом от 0.5 до 1.

Учёные решили разбить созвездие на k частей по результатам этого исследования. Для этого они исключат из рассмотрения k − 1 связь из данных и будут рассматривать получившиеся деревья. Оптимальным они считают такое разбиение, что:

k − 1∑i = 1e_i × k∏j = 1m_j→ max

Здесь e_i — это мощность i-й исключённой связи, а m_j — количество вершин в j-м из получившихся деревьев.

Формат входного файла

Первая строка входных данных содержит два целых числа n и k. Следующие n − 1 строки содержат по три числа каждая: номера звезд, соединённых связью, а также её мощность. Известно, что мощности связей, а также их структура, случайны.

Формат выходного файла

Выведите с максимально возможной точностью одно вещественное число — значение указанной функции для оптимального разбиения. Ответ считается корректным, если относительная погрешность не превышает 10^− 9.

Ограничения

1 ≤ n ≤ 100;

1 ≤ k ≤ n;

Примеры тестов

4 2
1 2 0.56234
2 3 0.85720
3 4 0.84552

3.42879999999999984794