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 độ dài đường đi ngắn nhất 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
4 6
2 7

Output 1

5
7
6