Đất nước ~XYZ~ gồm ~N~ thành phố được đánh số từ ~1~ đến ~N~. Có ~M~ đường dây dẫn có thể được xây dựng. Đường dây thứ ~i~ kết nối hai thành phố ~U_i~ và ~V_i~, với chi phí xây dựng là ~W_i~.

Chính phủ có kế hoạch xây dựng lưới điện quốc gia để cung cấp điện cho toàn bộ các thành phố. Họ sẽ đặt hai trạm phát điện tại hai thành phố khác nhau và xây dựng một số đường dây dẫn.

Một thành phố ~u~ được cung cấp điện nếu thành phố đó được đặt trạm phát điện hoặc có đường dây dẫn nối nó với một thành phố khác đã được cung cấp điện.

Chính phủ đề xuất ~Q~ phương án đặt trạm phát điện. Trong phương án thứ ~j~, hai trạm phát điện được đặt lần lượt tại hai thành phố ~A_j~ và ~B_j~.

Yêu cầu: Với mỗi phương án, hãy tính tổng chi phí nhỏ nhất để xây dựng các đường dây dẫn sao cho tất cả các thành phố đều được cung cấp điện.

Input

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~M~ ~(1 \le N \le 4 \times 10^3;\ 1 \le M \le 4 \times 10^5)~, lần lượt là số thành phố và số đường dây có thể xây dựng;

• Dòng thứ ~i~ trong ~M~ dòng tiếp theo gồm ba số nguyên ~U_i,V_i,W_i~ ~(1 \le U_i,V_i \le N;\ U_i \ne V_i;\ 1 \le W_i \le 10^9)~, mô tả đường dây thứ ~i~;

• Dữ liệu bảo đảm rằng nếu xây dựng toàn bộ ~M~ đường dây thì từ một thành phố bất kỳ có thể truyền điện đến mọi thành phố khác;

• Dòng tiếp theo chứa số nguyên ~Q~ ~(1 \le Q \le 2 \times 10^5)~, là số phương án;

• Dòng thứ ~j~ trong ~Q~ dòng tiếp theo gồm hai số nguyên ~A_j~ và ~B_j~ ~(1 \le A_j,B_j \le N;\ A_j \ne B_j)~, mô tả phương án thứ ~j~.

Output

Gồm ~Q~ dòng. Dòng thứ ~j~ chứa một số nguyên duy nhất là tổng chi phí nhỏ nhất cần thiết để tất cả các thành phố được cung cấp điện trong phương án thứ ~j~.

Scoring

Sample Input 1

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

Sample Output 1

14
13

Notes

Với phương án thứ nhất, hai trạm phát điện được đặt tại các thành phố ~4~ và ~5~. Có thể xây dựng các đường dây ~(1,2)~, ~(1,3)~, ~(1,5)~ và ~(4,6)~, với tổng chi phí bằng ~14~.

Với phương án thứ hai, hai trạm phát điện được đặt tại các thành phố ~6~ và ~4~. Có thể xây dựng các đường dây ~(1,2)~, ~(1,4)~, ~(1,5)~ và ~(3,5)~, với tổng chi phí bằng ~13~.