$N$ vacas ($2 \le N \le 1,000$), numeradas convenientemente $1,\ldots,N$, pastan en $N$ pastizales con los mismos números. Aún más cómodo, la vaca $i$ está en el pastizal $i$.

$N-1$ senderos bidireccionales conectan algunas parejas. El $i$ une $A_{i}$ y $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N$), longitud $L_{i}$ ($1 \le L_{i} \le 10,000$).

Entre cualquier pareja distinta hay exactamente una ruta, así que forman un árbol.

Son sociables, quieren visitarse a menudo y siempre tienen prisa. Ayuda a planificar calculando longitudes para $Q$ parejas ($1 \le Q \le 1,000$), consultas $p1,p2$ ($1 \le p1 \le N; 1 \le p2 \le N$).

Entrada

• Línea 1: enteros $N$, $Q$ separados por un espacio.
• Líneas $2,\ldots,N$: la línea $i+1$ contiene tres enteros separados por espacios $A_{i}$, $B_{i}$, $L_{i}$.
• Líneas $N+1,\ldots,N+Q$: dos enteros separados por un espacio $p1$, $p2$, pastizales distintos a visitar.

Salida

• Líneas $1,\ldots,Q$: la línea $i$ da la longitud de la consulta $i$.

Ejemplos

Entrada 1

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

Salida 1

2
7

Nota

Consulta 1: el sendero 1–2 mide 2. Consulta 2: recorrer 3–4, 4–1 y 1–2 da 7.

Subtareas

Puntos: 200

Créditos del problema: Neal Wu, 2007