Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Keliai medyje

Jums duotas svorinis medis su n viršūnių, bei q užklausų. Kiekvienai užklausa klausia, koks yra atstumas tarp tam tikrų dviejų viršūnių

Pradiniai duomenys

Pirmoje eilutėje pateikiami skaičiai n ir q (1\\leqn,q\\leq10^5) - medžio viršūnių bei užklausų skaičiai.

Tolesnėse n-1 eilutėse pateikiama po tris skaičius - a, b ir w (1\\leqa,b\\leqn,1\\leqw\\leq10^5) - jie reiškia, kad tarp viršūnių a ir b yra svorio w briauna.

Vėlesnėse q eilučių pateikiama po du skaičius - a ir b (1\\leqa,b\\leqn) - viršūnės, atstumą tarp kurių reikia išvesti.

Rezultatai

Vienintelėje eilutėje išveskite q tarpais atskirtų skaičių - atsakymus į užklausas.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 5
4 3 5
5 3 5
1 5 1
4 2 3
5 3
3 5
4 4
5 3
5 3
 
5 5 0 5 5