Restaurantes

Para comemorar o Dia das Mães Márcia decide levar sua tão amada mãe para almoçar em um restaurante. E como se trata de uma data especial ela se preocupa com todos os detalhes, principalmente, a distância e a qualidade da comida no restaurante.

Por isso, ela decide pegar um mapa de Fortal City, cidade em moram, para saber a distância dos restaurantes a sua casa e a casa de sua mãe. Ao analisar o mapa ela percebe que pode montar uma árvore ligando os restaurantes um aos outros e as suas casas respectivas casas. E agora ela já selecionou os melhores restaurantes mas precisa saber a distância entre eles e a sua casa, para então decidir onde ira almoçar com sua mãe.

Márcia vai lhe dar a árvore T que ela montou analisando o mapa da cidade e algumas perguntas do tipo:

• $$1$$ $$u$$ $$v$$ – Márcia quer saber a distância entre os restaurantes $$u$$ e $$v$$.
• $$2$$ $$u$$ $$v$$ $$k$$ – Márcia quer saber quem é o k-ésimo restaurante entre $$u$$ e $$v$$.

Ajude Márcia a responder suas perguntas e assim decidir qual será o restaurante perfeito para almoçar com sua mãe.

Entrada

A primeira linha da entrada contém dois inteiros $$N$$ e $$Q$$ $$(1 \leq N, Q \leq 10^5)$$, que representa a quantidade de restaurantes na árvore. As próximas $$N – 1$$ linhas contém cada uma três inteiros $$u$$, $$v$$ e $$d$$ que representam uma estrada entre os restaurantes $$u$$ e $$v$$ com $$d$$ $$m$$ de extensão. Cada uma das próximas $$Q$$ linhas contém uma pergunta de Márcia.

Saída

Imprima a resposta para cada uma das perguntas feitas por Márcia.

Exemplos

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

5
3