$N$ bò ($2 \le N \le 1,000$) tiện lợi đánh số $1,\ldots,N$, ăn cỏ ở $N$ đồng cũng đánh số vậy. Tiện nhất là bò $i$ ở đồng $i$.

$N-1$ đường hai chiều nối một số cặp đồng. Đường $i$ nối $A_{i}$, $B_{i}$ ($1 \le A_{i} \le N; 1 \le B_{i} \le N$), dài $L_{i}$ ($1 \le L_{i} \le 10,000$).

Giữa hai đồng khác nhau có đúng một tuyến đường, nên các đường tạo cây.

Bò thích giao lưu, muốn thăm nhau thường xuyên và luôn vội. Giúp lên lịch bằng tính độ dài cho $Q$ cặp ($1 \le Q \le 1,000$), mỗi truy vấn $p1,p2$ ($1 \le p1 \le N; 1 \le p2 \le N$).

Dữ liệu vào

• Dòng 1: số nguyên cách nhau bởi dấu cách $N$, $Q$.
• Các dòng $2,\ldots,N$: dòng $i+1$ chứa ba số nguyên cách nhau bởi dấu cách $A_{i}$, $B_{i}$, $L_{i}$.
• Các dòng $N+1,\ldots,N+Q$: hai số nguyên cách nhau bởi dấu cách $p1$, $p2$ cho hai đồng phân biệt cần đi giữa chúng.

Dữ liệu ra

• Các dòng $1,\ldots,Q$: dòng $i$ chứa độ dài đường của truy vấn $i$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
7

Ghi chú

Truy vấn 1: đường 1–2 dài 2. Truy vấn 2: qua 3–4, rồi 4–1, cuối 1–2, tổng 7.

Nhiệm vụ con

Điểm: 200

Ghi công bài toán: Neal Wu, 2007