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