Bình có một cây gồm \(N\) đỉnh, các đỉnh được nối với nhau bởi \(N-1\) cạnh, mỗi cạnh có trọng số. Bình muốn biết trên đường đi từ đỉnh \(u\) đến đỉnh \(v\), cạnh có trọng số nhỏ nhất là bao nhiêu.

Định dạng đầu vào

• Dòng đầu: hai số nguyên \(N, Q\) (\(1 \le N, Q \le 1000\)).
• \(N-1\) dòng tiếp: mỗi dòng \(u, v, w\) (\(1 \le u, v \le N, 1 \le w \le 10^6\)).
• \(Q\) dòng tiếp: mỗi dòng \(u, v\) là truy vấn.

Định dạng đầu ra

• Với mỗi truy vấn, in ra trọng số nhỏ nhất trên đường đi.

Ví dụ

Input:

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

Output:

3
2
5

Ràng buộc