Đất nước Y gồm ~N~ thành phố được đánh số từ ~1~ đến ~N~. Có ~M~ đường dây dẫn hai chiều có thể xây dựng được. Đường dây dẫn 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~. Giữa hai thành phố có thể có nhiều đường dây dẫn khác nhau.

Chính phủ của đất nước Y 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ọ dự định 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 để các thành phố đều được cung cấp điện. Một thành phố ~u~ được cung cấp điện nếu như thành phố ~u~ được đặt trạm phát điện, hoặc có một đường dây dẫn nối thành phố ~u~ 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 hai trạm phát điện. Với phương án thứ ~i~, hai trạm phát điện sẽ được đặt lần lượt tại hai thành phố ~A_i~ và ~B_i~.

Yêu cầu: Với mỗi phương án cần tính tổng chi phí tối thiểu để xây dựng các đường dây dẫn sao cho 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, M~ ~(2 \le N \le 4000, 1 \le M \le 400000)~ là số thành phố của đất nước Y và số đường dây dẫn có thể xây dựng.

• ~M~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~U_i, V_i~ và ~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 dẫn thứ ~i~. Dữ liệu đảm bảo đồ thị tạo bởi ~N~ thành phố và ~M~ đường dây là liên thông.

• Dòng tiếp theo gồm một số nguyên ~Q~ ~(1 \le Q \le 200000)~ là số phương án chính phủ đã đề xuất.

• ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~A_i~ và ~B_i~ ~(1 \le A_i, B_i \le N, A_i \ne B_i)~ mô tả phương án thứ ~i~.

Output

Với mỗi phương án, in ra một số nguyên duy nhất là tổng chi phí tối thiểu xây dựng các đường dây dẫn sao cho mỗi thành phố đều được cung cấp điện.

Scoring

Sample Input 1

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

Sample Output 1

14
13

Notes

• Với phương án thứ nhất, có thể xây các đường dây nối các cặp thành phố ~(1, 2)~, ~(1, 3)~, ~(1, 5)~ và ~(4, 6)~, với tổng chi phí là ~14~.

• Với phương án thứ hai, có thể xây các đường dây nối các cặp thành phố ~(1, 2)~, ~(1, 4)~, ~(1, 5)~ và ~(3, 5)~, với tổng chi phí là ~13~.