Mạng truyền thông

Ngân hàng AZ có $n$ chi nhánh, mỗi chi nhánh có một máy chủ là đầu mối đảm bảo truyền thông với các chi nhánh còn lại. Các máy chủ ở các chi nhánh được đánh số từ $1$ đến $n$. Để đảm bảo truyền thông giữa các chi nhánh, ngân hàng thuê $m$ kênh truyền tin của hai công ty A và B để kết nối $n$ máy chủ của các chi nhánh thành một mạng máy tính. Các kênh truyền tin được đánh số từ $1$ đến $m$, không có hai kênh truyền tin nào kết nối cùng một cặp máy chủ. Kênh truyền tin $i$ (thuê của công ty A hoặc B) đảm bảo việc truyền tin hai chiều giữa máy chủ của chi nhánh $u_i$ và $v_i$ ($i=1,2,\dots ,m$). Mạng máy tính có tính chất thông suốt nghĩa là đảm bảo từ máy chủ của một chi nhánh bất kỳ có thể truyền tin đến tất cả các máy chủ của các chi nhánh còn lại theo kênh truyền tin trực tiếp giữa chúng hoặc thông qua đường truyền đi qua một số máy chủ của các chi nhánh nào đó.

Trong thời gian tới do tình hình tài chính gặp khó khăn, ngân hàng muốn cắt giảm tối đa việc thuê các kênh truyền tin nhưng vẫn đảm bảo mạng thông suốt. Do chi phí thuê bao phụ thuộc vào số lượng kênh truyền tin phải thuê, nên sau khi hỏi ý kiến các chuyên gia, ngân hàng được biết là để đảm bảo tính thông suốt của mạng, tối thiểu phải thuê $n-1$ kênh truyền tin. Từ bảng đơn giá thuê bao kênh truyền tin với hai công ty ta biết $a_k$ và $b_k$ tương ứng là giá thuê bao $k$ kênh truyền tin của công ty A và B ($k=1,2,\dots ,n-1$). Nếu không giữ lại kênh nào của một công ty thì không phải trả tiền cho công ty đó. Ngân hàng muốn tìm phương án giữ lại đúng $n-1$ kênh truyền tin trong số $m$ kênh truyền tin đã thuê của hai công ty sao cho tổng chi phí thuê bao phải trả là nhỏ nhất mà vẫn đảm bảo tính thông suốt của mạng.

Yêu cầu: Cho biết danh sách các kênh truyền tin và các chi phí $a_k$, $b_k$ ($k=1,2,\dots ,n-1$). Hãy tìm phương án giữ lại đúng $n-1$ kênh truyền tin trong số $m$ kênh truyền tin đã thuê của hai công ty sao cho tổng chi phí thuê bao phải trả là nhỏ nhất mà vẫn đảm bảo tính thông suốt của mạng.

Dữ liệu vào

Dòng đầu tiên chứa $T$ là số lượng bộ dữ liệu. Tiếp đến là $T$ nhóm dòng, mỗi nhóm dòng cho biết thông tin về một bộ dữ liệu theo khuôn dạng sau:

• Dòng thứ nhất chứa hai số nguyên dương $n$, $m$;
• Dòng thứ hai chứa $n-1$ số nguyên dương $a_1,a_2,\dots ,a_{n-1}$, mỗi số nhỏ hơn ${10}^9$;
• Dòng thứ ba chứa $n-1$ số nguyên dương $b_1,b_2,\dots ,b_{n-1}$, mỗi số nhỏ hơn ${10}^9$;
• Dòng thứ $i$ trong số $m$ dòng tiếp theo chứa ba số nguyên dương $u_i$, $v_i$, $c_i$ cho biết thông tin về kênh truyền tin thứ $i$ ($i=1,2,\dots ,m$). Giả thiết $u_i$ khác $v_i$, $c_i=1$ nếu kênh truyền tin thuê của công ty A, $c_i=2$ nếu kênh truyền tin thuê của công ty B.

Các số trên cùng dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra

In ra $T$ dòng, mỗi dòng ghi kết quả của bộ dữ liệu tương ứng: chỉ số của $n-1$ kênh truyền tin được giữ lại, cách nhau bởi dấu cách. Nếu có nhiều cách thì in ra cách bất kì.

Ràng buộc

• $1\le T\le 10$.
• $2\le n\le {10}^4$; $n-1\le m\le {10}^5$.
• $1\le a_k,b_k<{10}^9$.
• $1\le u_i,v_i\le n$, $u_i\ne v_i$, không có hai kênh nối cùng một cặp máy chủ; mạng $m$ kênh ban đầu thông suốt.

Subtasks

• Subtask 1 ($30\%$ số điểm): $n<10$.
• Subtask 2 ($30\%$ số điểm): $n<100$.
• Subtask 3 ($40\%$ số điểm): $n\le {10}^4$, $m\le {10}^5$.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ