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