Cerința

Regele Leonidas trebuie să-și aleagă o armată de 300 de spartani. Surprins de mulțimea mare de voluntari care vor să-l urmeze în viitoarea luptă de la Termopile, regele are nevoie să facă o selecție a războinicilor. Astfel, el a decis să le dea următoarea problemă: 

Se dă un arbore cu N noduri (etichetate cu numere consecutive începând de la 1) cu rădăcina în nodul 1, în care fiecare muchie are asociat un cost. Se definește un lanț în jos în arbore ca fiind orice lanț simplu ce unește un nod A cu alt nod B din subarborele lui A. Cu alte cuvinte, un lanț în jos este un lanț de la A la B în care A este strămoș al lui B. Definim costul unui lanț în jos ca fiind suma costurilor muchiilor din care este format lanțul.

Numim acoperire a unui arbore o partiționare a muchiilor în lanțuri disjuncte, a căror reuniune este arborele inițial. Regele Leonidas dorește să acopere întreg arborele cu lanțuri în jos, însa are un număr limitat de lanțuri, notat în continuare cu S. 

Se cere să se determine cel mai mic număr K pentru care să existe o partiționare completă a arborelui cu maxim S lanțuri astfel încât costul fiecărui lanț să fie cel mult K. Dacă nu există un astfel de număr K, să se afișeze -1.

Pentru că și tu vrei să lupți alături de Leonidas pentru libertatea Spartei, trebuie să rezolvi această problemă ca să-ți asiguri un loc în primii 300 de spartani. Leonidas este un rege înțelept. Ca să se asigure că nu vor exista Spartani care vor încerca să ghicească rezultatul, el vă cere să răspundeți la T astfel de probleme. 

Date de intrare

Fişierul de intrare rege1.in conține pe prima linie numărul T, reprezentând numărul de teste din fişier. Urmează apoi cele T teste. Fiecare test este descris pe mai multe linii din fişier. Pe prima linie se află numerele N și S. Pe următoarele N-1 linii se află câte trei numere x y z, cu semnificația că există o muchie între nodurile x și y de cost z.

Date de ieșire

Fișierul rege1.out trebuie să conțină T linii, pe linia i se află răspunsul pentru testul i. 

Restricții și precizări

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 100 000
• 1 ≤ S ≤ 100 000
• 1 ≤ costul oricărei muchii ≤ 10 000

Exemplu:

rege1.in

2 
10 6 
2 1 1 
3 2 1 
4 1 3 
5 3 1 
6 5 2 
7 5 3 
8 2 2 
9 8 3 
10 5 2 
6 4 
2 1 4 
3 2 3 
4 3 2 
5 4 2 
6 4 4

rege1.out

4
4

Explicație

Avem T = 2 teste. 

Pentru primul test, avem un arbore cu N = 10 noduri.

Dorim să acoperim arborele cu maxim S = 6 lanțuri. Arborele se poate acoperi cu următoarele lanțuri:
 
1-4 (cost 3)
1-2-8 (cost 3)
8-9 (cost 3)
2-3-5-6 (cost 4)
5-10 (cost 2)
5-7 (cost 3)

Sunt exact 6 lanțuri (maxim 6 avem voie), iar costul cel mai mare al unui lanț e 4. Nu se poate face o acoperire cu cost maxim mai mic cu cel mult 6 lanțuri.

Pentru cel de-al doilea test, arborele are N = 6 noduri și dorim să-l acoperim cu maxim 4 lanțuri. Arborele se poate acoperi cu următoarele lanțuri: 

1-2 (cost 4) 
2-3 (cost 3) 
3-4-5 (cost 4) 
4-6 (cost 4) 

Sunt exact 4 lanțuri (maxim 4 avem voie), iar costul cel mai mare al unui lanț e 4. Nu se poate face o acoperire cu cost maxim mai mic cu cel mult 4 lanțuri.