$N$ vacas ($2 \le N \le 1,000$), convenientemente numeradas $1,\ldots,N$, pastam em $N$ pastos com os mesmos números. Melhor ainda, a vaca $i$ está no pasto $i$.

$N-1$ caminhos bidirecionais conectam alguns pares. O $i$ liga $A_{i}$ e $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N$), comprimento $L_{i}$ ($1 \le L_{i} \le 10,000$).

Entre qualquer par distinto há exatamente uma rota, portanto os caminhos formam uma árvore.

As vacas são sociáveis, querem visitar-se frequentemente e sempre têm pressa. Ajude a planejar calculando comprimentos para $Q$ pares ($1 \le Q \le 1,000$), consultas $p1,p2$ ($1 \le p1 \le N; 1 \le p2 \le N$).

Entrada

• Linha 1: inteiros $N$, $Q$ separados por um espaço.
• Linhas $2,\ldots,N$: a linha $i+1$ contém três inteiros separados por espaços $A_{i}$, $B_{i}$, $L_{i}$.
• Linhas $N+1,\ldots,N+Q$: dois inteiros separados por um espaço $p1$, $p2$, pastos distintos para viajar.

Saída

• Linhas $1,\ldots,Q$: a linha $i$ dá o comprimento da consulta $i$.

Exemplos

Entrada 1

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

Saída 1

2
7

Nota

Consulta 1: o caminho 1–2 mede 2. Consulta 2: percorrer 3–4, 4–1 e 1–2 totaliza 7.

Subtarefas

Pontos: 200

Créditos do problema: Neal Wu, 2007