Bittimaan rataverkko muodostuu n asemasta ja n-1 rataosuudesta niiden välillä. Miltä tahansa asemalta pääsee mille tahansa asemalle. Tehtäväsi on käsitellä joukko kyselyjä, joissa tehtävänä on laskea etäisyys kahden aseman välillä.

Syöte

Syötteen alussa on kaksi kokonaislukua n ja q: asemien määrä ja kyselyiden määrä. Asemat on numeroitu 1,2,\ldots,n.

Sitten syötteessä on n-1 riviä, jotka kuvavat rataosuudet. Jokaisella rivillä on kolme kokonaislukua a, b ja c: asemien a ja b välissä on rataosuus, jonka pituus on c. Kaikki rataosuudet ovat kaksisuuntaisia.

Lopuksi syötteessä on q riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua a ja b: tehtävänä on laskea etäisyys asemien a ja b välillä.

Tuloste

Tulosta vastaus jokaiseen kyselyyn.

Rajat

• 1 \le n,q \le 10^5
• 1 \le a,b \le n
• 1 \le c \le 10^9

Esimerkki

Syöte:

5 3
1 2 5
2 3 2
2 4 4
4 5 3
2 4
3 5
1 4

Tuloste:

4
9
9