Giải bài trực tuyến

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 ui và vi (i = 1, 2, ..., 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 ak và bk tương ứng là giá thuê bao k kênh truyền tin của công ty A và B (k = 1, 2, ..., 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.

Yêu cầu

Cho biết danh sách các kênh truyền tin và các chi phí ak, bk (k = 1, 2, ..., 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 a1, a2, ..., a(n - 1) mỗi số nhỏ hơn 10^9.
• Dòng thứ bai chứa n - 1 sô nguyên dương b1, b2, ..., 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 ui, vi, ci cho biết thông tin về kênh truyền tin thứ i (i = 1, 2, ..., m). Giả thiết ui khác vi, ci = 1 nếu kênh truyền tin thuê của công ty A, ci = 2 nếu kênh truyền tin thuê của công ty B.

Giải thích

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

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ì.

Example

Input:
1
3 3
1 2
1 5
1 2 1
1 3 2
2 3 2

Output:
1 3