18473번 - Fast Spanning Tree 다국어

Wang Xiuhan has an initially empty undirected graph on n vertices.

Each vertex has a weight, which is a non-negative integer.

Also, he has m tuples (a_i, b_i, s_i), where 1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, and s_i is a non-negative integer.

After that, he starts the following process:

• If there is no such i that a_i and b_i lie in different connected components of the graph and (total weight of vertices in the component of a_i) + (total weight of vertices in the component of b_i) ≥ s_i, end the process.
• Otherwise, choose the smallest such i, add an edge between a_i and b_i to the graph, write this i in the notepad, and repeat the process (but now on the larger graph).

After the process was completed, a misfortune happened... Someone stole his notepad! Can you help him restore all numbers efficiently?

The first line of input contains two integers n and m: the number of vertices in Xiuhan’s graph and the number of tuples he has (1 ≤ n, m ≤ 300 000).

The second line contains n space-separated integers, w₁, w₂, . . . , w_n: weights of the vertices (0 ≤ w_i ≤ 10⁶).

The next m lines contain a description of Xiuhan’s tuples. Each of these lines contains three integers a_i, b_i, s_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 0 ≤ s_i ≤ 10⁶).

On the first line, print one integer: the number of integers Xiuhan wrote in the notepad.

On the next line, you should write all these integers in the order he wrote them.