406256: GYM102331 F 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 \leq a_i, b_i \leq n$$$, $$$a_i \neq 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$$$) $$$\geq 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 \leq n, m \leq 300\,000$$$).

The second line contains $$$n$$$ space-separated integers, $$$w_1, w_2, \ldots, w_n$$$: weights of the vertices ($$$0 \leq w_i \leq 10^{6}$$$).

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 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$, $$$0 \leq s_i \leq 10^{6}$$$).

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.

5 5
1 4 3 4 0
4 5 5
3 1 1
2 5 2
4 3 1
4 1 4

4
2 3 1 4 

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

2
3 5