$N$ коров ($2 \le N \le 1,000$) удобно пронумерованы $1,\ldots,N$ и пасутся на $N$ пастбищах с теми же номерами. Удобнее всего, что корова $i$ на пастбище $i$.

Некоторые пары соединены $N-1$ двусторонними дорожками. Дорожка $i$ соединяет $A_{i}$ и $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N$), длина $L_{i}$ ($1 \le L_{i} \le 10,000$).

Между любыми разными пастбищами ровно один путь, значит дорожки образуют дерево.

Общительные коровы часто хотят навещать друг друга и всегда спешат. Помогите планировать визиты, вычисляя длины между $Q$ парами ($1 \le Q \le 1,000$); запросы $p1,p2$ ($1 \le p1 \le N; 1 \le p2 \le N$).

Входные данные

• Строка 1: целые $N$ и $Q$ через пробел.
• Строки $2,\ldots,N$: строка $i+1$ содержит три целых через пробел $A_{i}$, $B_{i}$, $L_{i}$.
• Строки $N+1,\ldots,N+Q$: два целых через пробел $p1$, $p2$ — разные пастбища для поездки.

Выходные данные

• Строки $1,\ldots,Q$: в строке $i$ длина пути запроса $i$.

Примеры

Входные данные 1

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

Выходные данные 1

2
7

Примечание

Запрос 1: путь 1–2 имеет длину 2. Запрос 2: дорожки 3–4, 4–1, затем 1–2 дают 7.

Подзадачи

Баллы: 200

Автор задачи: Neal Wu, 2007