Chính phủ đang triển khai một dự án quy hoạch giao thông quốc gia, bao gồm \(n\) tỉnh thành độc lập. Hiện tại, giữa các tỉnh chưa có tuyến đường nào được xây dựng.

Bộ Giao thông đã đề xuất \(m\) tuyến đường hai chiều tiềm năng. Mỗi tuyến nối hai tỉnh khác nhau và cần một khoản kinh phí nhất định để thi công. Tỉnh \(i\) có thể tự huy động tối đa \(c_i\) tỷ đồng cho dự án. Tuyến đường thứ \(j\) nối giữa hai tỉnh \(v_j\) và \(u_j\), với chi phí thi công là \(w_j\) tỷ đồng. Các tỉnh có thể góp ngân sách lại để cùng xây dựng đường. Khi hai tỉnh (hoặc hai cụm tỉnh đã kết nối) xây xong một tuyến đường, họ trở thành một liên vùng chung, và toàn bộ ngân sách còn lại của liên vùng sẽ được hợp nhất.

Nguyên tắc tài chính khi xây dựng:

• Một tuyến đường chỉ có thể được xây nếu tổng ngân sách hiện có của hai liên vùng liên quan lớn hơn hoặc bằng chi phí \(w_j\).
• Sau khi xây xong, hai liên vùng được hợp nhất, và ngân sách còn lại bằng tổng hai bên trừ đi \(w_j\).

Yêu cầu: Xác định xem có thể chọn một tập hợp các tuyến đường và sắp xếp thứ tự thi công sao cho tất cả các tỉnh đều được kết nối giao thông với nhau hay không. Nếu có thể, hãy đưa ra thứ tự các tuyến cần thi công.

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(m\) (\(1 \le n \le 10^6\), \(0 \le m \le 10^6\)) là số tỉnh thành và số tuyến đường được đề xuất.
• Dòng thứ hai chứa \(n\) số nguyên \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 10^6\)) là ngân sách hiện có của mỗi tỉnh.
• Mỗi dòng trong \(m\) dòng tiếp theo chứa ba số nguyên \(v_i, u_i, w_i\) (\(1 \le v_i, u_i \le n\), \(1 \le w_i \le 10^6\)) là hai tỉnh được nối và chi phí thi công tuyến đường giữa chúng (các tuyến đường được đánh số thứ tự từ \(1\) đến \(m\) theo thứ tự xuất hiện).

Output

• Nếu không thể thi công đủ tuyến để kết nối toàn bộ đất nước, in ra -1.
• Nếu có thể:
  • Dòng đầu tiên in ra số lượng tuyến đường \(q\) được thi công.
  • Dòng tiếp theo in ra \(q\) số nguyên là chỉ số của các tuyến đường theo đúng thứ tự thi công.

Example

3 2
2 2 10
1 2 5
2 3 8

2
2 1

Scoring

• Subtask \(1\) (\(10\) điểm): \(n, m \le 10\).
• Subtask \(2\) (\(15\) điểm): \(n, m \le 10^5\) và \(c_i = 1\).
• Subtask \(3\) (\(15\) điểm): \(n, m \le 10^5\) và tất cả \(w_i\) bằng nhau.
• Subtask \(4\) (\(15\) điểm): \(n, m \le 10^3\).
• Subtask \(5\) (\(20\) điểm): \(n, m \le 10^5\).
• Subtask \(6\) (\(25\) điểm): Không có ràng buộc nào thêm.