Có \(N\) con bò (\(1≤N≤10^5\)), để thuận tiện ta đánh số từ \(1→N\), đang ăn cỏ trên \(N\) đồng cỏ, để thuận tiện ta cũng đánh số các đồng cỏ từ \(1→N\). Biết rằng con bò \(i\) đang ăn cỏ trên đồng cỏ \(i\).

Một vài cặp đồng cỏ được nối với nhau bởi 1 trong \(N-1\) con đường 2 chiều mà các con bò có thể đi qua. Con đường \(i\) nối 2 đồng cỏ \(A_i\) và \(B_i\) (\(1≤A_i,B_i≤N\))và có độ dài \(L_i\) (\(1≤L_i≤10^4\) ).

Các con đường được thiết kế sao cho với 2 đồng cỏ bất kỳ đều có duy nhất 1 đường đi giữa chúng. Như vậy các con đường này đã hình thành 1 cấu trúc cây.

Các chú bò rất có tinh thần tập thể và muốn được thăm thường xuyên. Vì vậy lũ bò muốn bạn giúp chúng tính toán độ dài đường đi giữa \(Q\ (1≤Q≤1000)\) cặp đồng cỏ (mỗi cặp được mô tả là 2 số nguyên u,v (\(1≤u,v≤N\)).

Dữ liệu

• Dòng đầu ghi 2 số nguyên cách nhau bởi dấu cách: \(N\) và \(Q\)
• \(N-1\) dòng tiếp theo: Mỗi dòng chứa 3 số nguyên cách nhau bởi dấu cách: \(A_i,B_i\) và \(L_i\), mô tả có đường đi trực tiếp giữa \(A_i,B_i\) và độ dài của nó là \(L_i\)
• \(Q\) dòng tiếp theo: Mỗi dòng chứa 2 số nguyên (\(u,v\)) khác nhau yêu cầu tính toán độ dài 2 đồng cỏ mà lũ bò muốn đi thăm qua lại.

Kết quả

• Ghi \(Q\) số là kết quả của từng yêu cầu theo thứ tự, mỗi số viết trên một dòng.

Input

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

Output

2
7

Giải thích Đường đi từ \(1→2\) độ dài \(2\). Đường đi từ \(3→2\) độ dài \(7\).

Nguồn: CD DHBB 2020