$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