Яблоня называется двоичной, если в каждой точке ветвления ствол или ветвь разветвляется надвое. Точки ветвления, корень и концы веток - это узлы дерева. Известна масса каждого участка яблони между двумя соседними узлами. Первоначально в яблоне N узлов, а нужно оставить M. Яблоню можно резать в основаниях ветвей, при этом ветвь и вся часть дерева, растущая выше, удаляются.

Исходные данные: N, M (1 < M < N ≤ 100) и список из N-1 тройки. Каждая тройка содержит номера узлов, определяющих участок и его массу (узлы перенумерованы от 1 до N).

Напишите программу, которая вводит исходные данные и находит план подрезки дерева, оставляющий наименьшую суммарную массу оставшихся участков.

Например, для исходных данных: N=8, M=3 и набора троек (1, 2, 19), (2, 4, 13), (3, 2, 12), (3, 8, 17), (3, 6, 11), (5,8,10) и (8,7,8), вывод программы может быть следующим:

    
Обрезать ветки: (2,4),(3,8),(3,6).