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