Informática Intermediário - Semana 57

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

Entrada

Saída

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