Đấ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ể 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}\).

Chính phủ của đất nước XYZ 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ứ \(j\), hai trạm phát điện sẽ được đặt lần lượt tại hai thành phố \(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 thành phố đề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 người dân trong đất nước XYZ.

Dữ liệu vào:

+ Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \leq n \leq 4 \times 10^{3}\), \(1 \leq m \leq 4 \times 10^{5}\)) là số thành phố của đất nước XYZ 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}\) (\(1 \leq u_{i}\), \(v_{i} \leq n\), \(u_{i}
eq v_{i}\), \(1 \leq w_{i} \leq 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ừ thành phố bất kì đều có thể truyền điện đến một thành phố 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\) (\(1 \leq q \leq 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}\) (\(1 \leq a\), \(b_{j} \leq n\), \(a_{j}
eq b_{j}\)) mô tả phương án thứ \(j\).

Kết quả:

+ Ghi \(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 thành phố đều được cung cấp điện với phương án thứ \(j\).

Ví dụ:

Input	Output
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	14 13

Giải thích: 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).

Ràng buộc:

+ Có 10% số test có \(n,\ m \leq 15;q \leq 100\);

+ Có 25% số test khác có \(q = 1\);

+ Có 40% số test khác có \(q \leq 3000\);

+ Có 25% số test còn lại không có ràng buộc gì thêm.