$N$ krów ($2 \le N \le 1,000$), wygodnie numerowanych $1,\ldots,N$, pasie się na tak samo numerowanych $N$ pastwiskach. Najwygodniej, że krowa $i$ jest na pastwisku $i$.

$N-1$ dwukierunkowych ścieżek łączy niektóre pary. Ścieżka $i$ łączy $A_{i}$ i $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N$), długość $L_{i}$ ($1 \le L_{i} \le 10,000$).

Między każdymi różnymi pastwiskami jest dokładnie jedna droga, więc ścieżki tworzą drzewo.

Towarzyskie krowy chcą częstych wizyt i zawsze się spieszą. Pomóż planować, licząc długości dla $Q$ par ($1 \le Q \le 1,000$), zapytania $p1,p2$ ($1 \le p1 \le N; 1 \le p2 \le N$).

Wejście

• Wiersz 1: całkowite $N$, $Q$ ze spacją.
• Wiersze $2,\ldots,N$: wiersz $i+1$ zawiera trzy całkowite ze spacjami $A_{i}$, $B_{i}$, $L_{i}$.
• Wiersze $N+1,\ldots,N+Q$: dwa całkowite ze spacją $p1$, $p2$, różne pastwiska podróży.

Wyjście

• Wiersze $1,\ldots,Q$: wiersz $i$ zawiera długość drogi zapytania $i$.

Przykład

Wejście 1

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

Wyjście 1

2
7

Uwagi

Zapytanie 1: ścieżka 1–2 ma długość 2. Zapytanie 2: 3–4, potem 4–1, w końcu 1–2 dają 7.

Podzadania

Punkty: 200

Autor zadania: Neal Wu, 2007