Cho cây giao thông gồm \(N\) trạm và \(N-1\) con đường có độ dài. Hãy trả lời nhanh \(Q\) truy vấn khoảng cách ngắn nhất giữa hai trạm \(u\) và \(v\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(2 \le N, Q \le 200000\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v\) và \(w\) (\(1 \le u, v \le N\), \(1 \le w \le 10000\)) mô tả một con đường nối \(u\) và \(v\) có chiều dài \(w\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) mô tả truy vấn.

Kết quả ra

• In ra khoảng cách ngắn nhất cho mỗi truy vấn trên một dòng mới.

Ví dụ

Input

4 2
1 2 10
2 3 20
2 4 15
3 4
1 3

Output

35
30