Cho cây cáp treo kết nối \(N\) đỉnh núi bằng \(N-1\) tuyến cáp treo. Mỗi tuyến cáp treo có một độ rung lắc khác nhau.

Hãy trả lời \(Q\) truy vấn: Tìm độ rung lắc lớn nhất của cabin khi di chuyển trên hành trình đơn giữa trạm u và trạm \(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 10^9\)) mô tả độ rung lắc w của cáp treo nối giữa u và \(v\).
• \(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 độ rung lắc lớ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 5
2 4 12
3 4
1 4

Output

12
10

Ràng buộc & Subtasks