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

Ràng buộc & Subtasks