Cho một cấu trúc cây đường bộ gồm \(N\) trạm và \(N-1\) cây cầu nối giữa chúng. Mỗi cây cầu có một mức tải trọng giới hạn khác nhau.

Hãy trả lời \(Q\) truy vấn: Tìm mức tải trọng giới hạn nhỏ nhất trên con đường đi đơ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ả tải trọng giới hạn \(w\) của cây cầu nối \(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

• Với mỗi truy vấn, in ra tải trọng giới hạn nhỏ nhất 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

5
10