Дельта Квадрант
Більша частина Дельта Квадранта залишається недослідженою, проте відомо, що існує багато небезпечних районів, населених ворогуючими расами. Тим не менш, є кілька оголошених нейтральних зон, розташованих між планетами, якими можна безпечно подорожувати.
Планується критичний саміт, але він відбудеться лише за умови досягнення кворуму з її членів. Для цього майже всі делегати з Дельта Квадранта повинні бути доставлені в одне місце, звідки Ентерпрайз їх забере на саміт.
Ентерпрайз прямує до Дельта Квадранта. Ви повинні знайти найшвидший спосіб, як за допомогою одного корабля відправитися з однієї з планет Дельта Квадранта і повернутися на цю ж планету, відвідавши всі, крім заданих планет.
Маємо n планет і n - 1 безпечних шляхів, що проходять через нейтральні зони, з'єднуючи планети. Для кожного шляху відомий час його подолання. Знайдіть найменший час, за який, стартуючи з довільної планети, можна відвідати n - k планет і повернутися назад.
Вхідні дані
Перший рядок містить кількість тестів t (1 ≤ t ≤ 50). Кожен тест починається з рядка, що містить два числа: кількість планет n (2 ≤ n ≤ 10000) і число планет k (0 ≤ k ≤ min(n - 1, 20)), які не слід відвідувати. Кожен з наступних n - 1 рядків містить три цілі числа - початкова і кінцева планети (від 0 до n - 1) і час подолання шляху. Час лежить в інтервалі від 0 до 1000000 включно. Вхідний граф є зв'язним.
Вихідні дані
Для кожного тесту виведіть в окремому рядку найменший час подорожі.