Cho một cây có trọng số \(n\) đỉnh, có đỉnh gốc là \(1\). Cho \(q\) truy vấn có dạng \((u,v)\), tìm trọng số cạnh lớn nhất trên đường đi đơn giữa \(u\) và \(v\).

Dữ liệu vào

• Dòng đầu tiên gồm \(2\) số nguyên \(n,q\).
• \(n-1\) dòng tiếp theo, mỗi dòng gồm \(3\) số nguyên \(u,v,w\) thể hiện có cạnh nối \(u\) và \(v\) trọng số \(w\).
• \(q\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(u,v\), một truy vấn.

Dữ liệu ra

• In ra \(q\) số nguyên, đáp án cho \(q\) truy vấn.

Điều kiện

• \(1 \le n,q \le 10^5\)
• \(1 \le u,v \le n\)
• \(1 \le w \le 10^9\)

Input 1

7 3
1 2 1
1 3 2
2 4 3
2 5 2
3 6 1
3 7 3
4 5
2 6
2 1

Output 1

3
2
1