Las $N$ vacas $(1\le N\le 1000)$ convenientemente numeradas $1$...$N$ están pastando entre los $N$ pastizales también numerados convenientemente $1$...$N$. Aún más, la vaca $i$ está pastando en el pastizal $i$.

Algunos pares de pastizales están conectados por $N-1$ senderos bidireccionales que pueden ser recorridos por las vacas. El sendero $i$ conecta los pastizales $A_i$ y $B_i$ $(1\le A_i\le N;1\le B_i\le N)$ y tiene una longitud de $L_i$ $(1\le L_i\le 10000)$.

Los senderos están organizados de manera tal que entre cualesquiera dos pastizales distintos, existe un camino de senderos que va entre ellos. Por lo tanto, los senderos forman un árbol.

Las vacas son muy sociales y quieren visitarse entre ellas frecuentemente. Siempre apuradas, ellas quieren que usted les ayude a planificar sus visitas calculando las longitudes de caminos entre $Q$ $(1\le Q\le 1000)$ pares de pastizales (cada par está dado como una pregunta $p1,p2(1\le p1\le N,1\le p2\le N)$.

Entrada

Línea 1: Dos enteros separados por espacio: $N$ y $Q$.

Líneas 2..N: La línea $i+1$ contiene tres enteros separados por espacios: $A_i$, $B_i$ y $L_i$.

Líneas N+1..N+Q: Cada línea contiene dos enteros separados por espacio representando dos pastizales distintos entre los cuales las vacas quieren viajar: $p1$ y $p2$.

Salida

Líneas 1..Q: La línea $i$ contiene la longitud del camino entre los dos pastizales en la pregunta $i$.

Ejemplo de Entrada

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

Ejemplo de Salida

2
7

Explicación

Pregunta 1: El sendero entre los pastizales $1$ y $2$ tiene longitud $2$.

Pregunta 2: Viaje a través del sendero entre los pastizales $3$ y $4$, luego a través del que está entre $4$ y $1$, y finalmente a través del que está entre $1$ y $2$, para una longitud total de $7$.