Mạng giao thông của đất nước Peace xinh đẹp có ~n~ thành phố được nối với nhau bằng hệ thống các đường cao tốc. Vì lý do kinh tế nên nhà vua chỉ xây dựng ~n-1~ con đường đủ đảm bảo sự đi lại giữa hai thành phố bất kỳ. Tất nhiên, mỗi con đường có lệ phí riêng.

Công ty lữ hành ABC nhận được ~m~ yêu cầu thuê xe của ~m~ khách hàng. Mỗi yêu cầu thể hiện như là một cặp hai thành phố ~s, t~ - yêu cầu di chuyển từ thành phố ~s~ đến thành phố ~t~ chỉ bằng đường cao tốc. Tất nhiên, Ban Giám đốc công ty muốn rằng tổng lệ phí giao thông phải trả cho các con đường trên hành trình từ ~s~ đến ~t~ phải là nhỏ nhất.

Yêu cầu: Với mỗi yêu cầu thuê xe, hãy giúp Ban Giám đốc tính toán tổng lệ phí giao thông ít nhất phải trả để thực hiện yêu cầu này.

Input

Vào từ tệp MINCOST.INP:

• Dòng đầu chứa hai số nguyên ~n, m\ (1\le n,m \le 10^5)~;
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i, v_i, w_i~ thể hiện có tuyến đường cao tốc hai chiều nối thành phố ~u_i~ với thành phố ~v_i~ và có lệ phí giao thông là ~w_i\ (1\le u_i,v_i \le n;\ w_i \le 10^5)~
• ~m~ dòng tiếp theo, dòng thứ ~j~ ghi hai số nguyên ~s_i, t_i\ (1\le s_j, t_j \le n)~ thể hiện yêu cầu thứ ~j~ đối với công ty: Thuê xe đi từ thành phố ~s_j~ tới thành phố ~t_j~.

Output

Ghi ra tệp MINCOST.OUT:

• Gồm ~m~ dòng, dòng thứ ~j~ ghi một số nguyên là chi phí ít nhất phải trả khi thực hiện yêu cầu ~j\ (j \in [1;m])~

Ví dụ

MINCOST.INP

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

MINCOST.OUT

9
6
11
14