$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