G. Тестване 
---
Последните години Джени напредна много в състезателната информатика и вече не само че може да решава много задачи, но и започна да предлага свои. Но целият процес около написване на генератор, със средно 200-300 реда код, и генериране на тестовете ѝ е омръзнал. Новата задача, по която работи Джени, е със следното условие: "Дадено е претеглено дърво с N върха и константата K. Задачата е да се намери такова множество от ребра E, с минимална сума на теглата на ребрата в него, че като се премахнат ребрата от E от дървото, да се получи дърво (или поддърво) с K върха."
 
За да си спести усилия, Джени решила да копира тестове от друга своя задача, в която също е зададено претеглено дърво, като за всеки тест само добави произволно K. Тъкмо привършила с промените в тестовете и започнала да пише пример в условието и … изненада! Нейното решение давало грешен отговор на примера, който измислила. Съответно, не е много ясно доколко верни са отговорите и за останалите тестове, които е използвала. Затова се обръща с голяма молба към Вас, да сте неин тестер, като напишете програма, която по зададени тестове, намира отговорите им. 

Вход: На първия ред на стандартния вход ще бъде зададен броят на тестовете T, които програмата трябва да реши при едно извикване, а на следващите редове ще бъдат данните за тестовете. За всеки тестов пример на първия ред на стандартния вход ще бъдат зададени целите N и K – броят върхове в дървото и броят на върховете в дървото/поддървото, което трябва да се отдели. На всеки от следващите N – 1 реда на тестовия пример ще бъдат зададени по три цели числа x, y и t, които показват, че има ребро в зададеното дърво между върховете с номера x и y, а тегло на това ребро е t (върховете са номерирани с числата от 1 до N). 

Изход: За всеки тест, по реда им на въвеждане, програмата трябва да изведе на отделен ред на стандартния изход минималната сума от теглата на ребрата, които да бъдат премахнати така, че да получим поне едно дърво със зададения брой върхове.
 
Ограничения: 1 ≤ N ≤ 10^3; 1 ≤ K ≤ min(N, 2.10^2); 1 ≤ x, y ≤ N; 1 ≤ t ≤ 10^6.  

Примерен вход: 
2
6 3
1 2 3
1 3 1
2 4 1
2 5 2
2 6 1
5 2
1 2 3
1 3 1
2 4 1
2 5 2

Примерен изход:
3
3