Mùa này IUH rất hay cúp điện. Ở IUH có ~N~ tòa nhà được đánh số từ ~1~ đến ~N~. Có ~M~ đường dây dẫn có thể xây dựng được, đường dây dẫn thứ ~i~ kết nối hai tòa nhà ~U_i~ và ~V_i~ với chi phí xây dựng là ~W_i~.

Các sếp của IUH có kế hoạch xây dựng lưới điện riêng để cung cấp điện cho toàn bộ các tòa nhà. Họ dự định sẽ đặt hai trạm phát điện tại hai tòa nhà khác nhau, và xây dựng một số đường dây dẫn để các tòa nhà đều được cung cấp điện. Một tòa nhà ~u~ được cung cấp điện nếu như tòa nhà ~u~ được đặt trạm phát điện, hoặc có một đường dây dẫn nối tòa nhà ~u~ với một tòa nhà khác được cung cấp điện.

Họ đã đề xuất ~Q~ phương án đặt hai trạm phát điện. Với phương án thứ ~j~, hai trạm phát điện sẽ được đặt lần lượt tại hai tòa nhà ~A_j~ và ~B_j~. Với mỗi phương án, họ 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 tòa nhà đều được cung cấp điện. Yêu cầu: bạn hãy giúp chính phủ thực hiện các phương án trên để phục vụ nhu cầu của SV IUH nhé.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ với ~1≤N≤4×10^3, 1≤M≤4 \times 10^5~ là số tòa nhà của IUH và số lượng đường dây dẫn có thể xây dựng.

Dòng thứ ~i~ trong ~M~ dòng tiếp theo chứa ba số nguyên ~U_i, V_i~ và ~W_i~ với ~1≤U_i, V_i≤N, U_i≠V_i, 1≤W_i≤10^9~ mô tả đường dây dẫn thứ ~i~. Dữ liệu vào đảm bảo rằng nếu xây dựng toàn bộ ~M~ đường dây, từ tòa nhà bất kì đều có thể truyền điện đến một tòa nhà khác thông qua các đường dây dẫn.

Dòng tiếp theo chứa một số nguyên ~Q~ với ~1≤Q≤2 \times 10^5~ là số lượng phương án mà chính phủ đã đề xuất. Dòng thứ ~j~ trong ~Q~ dòng tiếp theo chứa hai số nguyên ~A_j~ và ~B_j~ với ~1≤A_j, B_j≤N, A_j≠B_j~ mô tả phương án thứ ~j~.

Output

Kết quả gồm ~Q~ dòng, dòng thứ ~j~ 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 tòa nhà đều được cung cấp điện với phương án thứ ~j~.

Sample input

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

14
13

Hình ảnh bên minh họa phương án thứ nhất và thứ hai của test ví dụ (cạnh nét đứt là các đường dây dẫn có thể xây dựng, cạnh nét liền là các đường dây dẫn cần xây dựng, đỉnh đen là các thành phố được đặt trạm phát điện).

Subtasks

• 10% số điểm ứng với ~𝑁, 𝑀 ≤ 15, 𝑄 ≤ 100~
• 25% số điểm ứng với ~𝑄 = 1~
• 40% số điểm ứng với ~𝑄 ≤ 3000~
• 25% số điểm ứng với giới hạn đề bài.