(conbo.*)

Có \(n\) con bò, để thuận tiện ta đánh số từ 1 đến \(n\), đang ăn trên \(n\) đồng cỏ, để thuận tiện ta cũng đánh số các cánh đồng cỏ từ 1 đến \(n\). Biết rằng con bò thứ \(i\) đang ăn trên đồng cỏ thứ \(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 được. Con đường thứ \(i\) nối 2 cánh đồng cỏ \(a_{i}\) và \(b_{i}\) và có độ dài \(c_{i}\).

Các con đường được thiết kế sao cho với 2 cánh đồng cỏ bất kỳ đều có duy nhất 1 đường đi giữa chúng.

Các con bò rất có tinh thần giao lưu vì vậy chúng thường xuyên qua lại lẫn nhau.

Yêu cầu: Bạn hãy giúp các con bò tính toán độ dài đường đi qua giữa \(q\) cặp đồng cỏ, mỗi cặp đồng cỏ mô tả 2 số nguyên \(u,\ v\ (1\ \leq \ u\ ,\ v \leq n)\).

Dữ liệu vào:

• Dòng đầu tiên ghi 2 số nguyên \(n\) và \(q\) cách nhau bởi dấu cách \((1 \leq n \leq \ 10^{5};\ 1 \leq q \leq 50000)\);

• \(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};\ c_{i}\) mô tả đường đi trực tiếp giữa \(a_{i},\ b_{i}\) và độ dài của nó là \(c_{i}\ (1 \leq a_{i},\ b_{i} \leq n;\ 1 \leq c_{i}\ \leq {10}^{5})\);

• \(q\) dòng tiếp theo: Mỗi dòng chứa 2 số nguyên \(u\) và \(v\) khác nhau yêu cầu tính toán độ dài đường đi giữa 2 đồng cỏ mà các con bò muốn đi thăm qua lại.

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

Ví dụ:

Ràng buộc: Có 50% số test có \(n\ \leq \ 5000\).