$N$ mucche ($2 \le N \le 1,000$), comodamente numerate $1,\ldots,N$, pascolano in $N$ pascoli con gli stessi numeri. Ancora meglio, la mucca $i$ è nel pascolo $i$.

$N-1$ sentieri bidirezionali collegano alcune coppie. Il sentiero $i$ collega $A_{i}$ e $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N$), lunghezza $L_{i}$ ($1 \le L_{i} \le 10,000$).

Tra ogni coppia distinta c’è esattamente un percorso: i sentieri formano un albero.

Socievoli e sempre di fretta, vogliono visitarsi spesso. Aiutate a pianificare calcolando lunghezze per $Q$ coppie ($1 \le Q \le 1,000$), richieste $p1,p2$ ($1 \le p1 \le N; 1 \le p2 \le N$).

Input

• Riga 1: interi $N$, $Q$ separati da uno spazio.
• Righe $2,\ldots,N$: la riga $i+1$ contiene tre interi separati da spazi $A_{i}$, $B_{i}$, $L_{i}$.
• Righe $N+1,\ldots,N+Q$: due interi separati da uno spazio $p1$, $p2$, pascoli distinti tra cui viaggiare.

Output

• Righe $1,\ldots,Q$: la riga $i$ dà la lunghezza della richiesta $i$.

Esempi

Input 1

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

Output 1

2
7

Nota

Richiesta 1: il sentiero 1–2 misura 2. Richiesta 2: 3–4, poi 4–1, infine 1–2 totalizzano 7.

Sottoproblemi

Punti: 200

Crediti del problema: Neal Wu, 2007