Большая часть Дельта Квадранта остается неисследованной, однако известно, что существует множество опасных районов, населенных враждующими расами. Тем не менее, существует небольшое количество объявленных нейтральных зон, расположенных между планетами, которыми можно безопасно путешествовать. Планируется критический саммит, однако он произойдет только когда будет достигнут кворум из ее членов. Для достижения этого кворума почти все делегаты от Дельта Квадранта должны быть доставлены в одно место, откуда Энтерпрайз их уже заберет на саммит. Энтерпрайз находится на пути к Дельта Квадранту. Вы должны найти самый быстрый способ, как с помощью одного корабля отправится из одной из планет Дельта Квадранта и возвратиться на эту же планету, чтобы при этом посетить все кроме заданных планет. Имеется \textbf{n }планет и \textbf{n - 1 }безопасных путей проходящих через нейтральные зоны, соединяющих планеты. Для каждого пути известно время его преодоления. Найдите наименьшее время, за которое стартовав с произвольной планеты, можно посетить \textbf{n - k }планет и вернуться обратно. \InputFile Первая строка содержит количество тестов \textbf{t} (\textbf{1} ≤ \textbf{t }≤ \textbf{50}). Каждый тест начинается со строки, содержащей два числа: количество планет \textbf{n} (\textbf{2 }≤ \textbf{n }≤ \textbf{10000}) и число планет \textbf{k} (\textbf{0} ≤ \textbf{k }≤ \textbf{min(n - 1},\textbf{ 20)}), которое не следует посещать. Каждая из следующих \textbf{n - 1} строк содержит три целых числа - начальная и конечная планеты (от \textbf{0 }до \textbf{n - 1}) и время преодоления пути. Время лежит в интервале от \textbf{0 }до \textbf{1000000} включительно. Входной граф является связным. \OutputFile Для каждого теста выведите в отдельной строке наименьшее время путешествия.