Cho một cây có trọng số gồm ~n~ đỉnh, gốc tại đỉnh ~1~.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v)~ — hãy tìm khoảng cách ngắn nhất giữa ~u~ và ~v~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~, ~w~ — có một cạnh trọng số ~w~ 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ả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Đầu vào:

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

Đầu ra:

5
7
6

Giải thích: Đường đi từ ~4~ đến ~5~ là ~4 \to 2 \to 5~ với chi phí ~3 + 2 = 5~. Đường đi từ ~4~ đến ~6~ là ~4 \to 2 \to 1 \to 3 \to 6~ với chi phí ~3 + 1 + 2 + 1 = 7~.

Giới hạn

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

Khoảng cách có thể lên tới ~10^{14}~ nên không vừa trong số nguyên 32 bit. Nếu ~u = v~ thì đáp án là ~0~.