Kế hoạch chơi game của Thành để giảm stress đã bị phá sản. Giờ đây anh ấy rơi vào trầm cảm. Nên anh ấy nhờ một người bạn đề xuất đi du lịch để giải tỏa căng thẳng.

Địa điểm mà Thành chuẩn bị đến được biểu diễn bằng ~N~ thành phố và ~N - 1~ tuyến đường giao thông. Những tuyến đường hai chiều này đảm bảo việc di chuyển từ một thành phố đến thành phố khác luôn luôn khả thi.

Dự định của Thành và người bạn sẽ đi tham quan giữa hai thành phố, tức là họ sẽ đi từ thành phố ~U~ đến thành phố ~V~ để tham quan. Người bạn của Thành đã chọn ra được ~Q~ kế hoạch để tham quan. Nhưng do Thành đã bị trầm cảm nên người bạn của anh ta đã quyết định tính toán xem chi phí đi du lịch là bao nhiêu sau đó mới hỏi ý kiến của Thành. Chi phí của chuyến du lịch bằng tổng quãng đường đi tham quan cộng với tổng chi phí hao hụt của chuyến đi. Chi phí hao hụt được tính bằng 1 khi họ dừng lại tại một thành phố để nghỉ ngơi, biết rằng họ luôn dừng lại tham quan khi đi qua một thành phố nào đó trên đường đi (Tính cả thành phố xuất phát và thành phố đích).

Yêu cầu: Với mỗi kế hoạch gồm hai thành phố ~S, T~, hãy tính tổng chi phí chuyến đi.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N, Q~ lần lượt là số thành phố được chọn trong chuyến du lịch và số kế hoạch dự định (~N, Q \le 10^5~).
• ~N - 1~ dòng tiếp theo gồm 3 số nguyên dương ~U_i, V_i, W~ lần lượt là tuyến đường của địa điểm đó và khoảng cách giữa hai thành phố (~U, V \le N, W \le 10^9~).
• ~Q~ dòng tiếp theo gồm hai ~S, T~ là hai thành phố nằm trong kế hoạch du lịch (~S, T \le N~).

Output

• Gồm ~Q~ dòng là kết quả của bài toán.

Sample Input 1

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

Sample Output 1

10 
4 

Sample Input 2

6 3 
1 2 2 
1 3 4 
3 4 4 
3 5 3 
2 6 1 
1 4 
2 3 
4 5

Sample Output 2

11 
9 
10