VOI 14 Bài 3 - Mạng truyền thông


Submit solution

Points: 1.36 (partial)
Time limit: 1.5s
Memory limit: 512M

Problem type

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, \ldots, 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êu 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, \ldots, n - 1\)). 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.

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, \ldots, 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.

Input

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, \ldots, a_{n - 1}\) mỗi số nhỏ hơn \(10^9\).
  • Dòng thứ bai chứa \(n - 1\) sô nguyên dương \(b_1, b_2, \ldots, 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, \ldots, 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.

Output

Ghi ra \(T\) dòng, mỗi dòng ghi kết quả của bộ test tương ứng: chỉ số những cạnh được giữ lại.

Nếu có nhiều cách thì in ra cách bất kì.

Giới hạn

  • 30% số test có \(n < 10\).
  • 30% số test khác có \(n < 100\).
  • 40% số test còn lại có \(n \le 10^4\), \(m \le 10^5\).

Sample Input

1
3 3
1 2
1 5
1 2 1
1 3 2
2 3 2

Sample Output

1 2

Comments

There are no comments at the moment.