시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 41 25 11 57.895%

문제

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 (ai, bi, si), where 1 ≤ ai, bi ≤ n, ai ≠ bi, and si is a non-negative integer.

After that, he starts the following process:

  • If there is no such i that ai and bi lie in different connected components of the graph and (total weight of vertices in the component of ai) + (total weight of vertices in the component of bi) ≥ si, end the process.
  • Otherwise, choose the smallest such i, add an edge between ai and bi 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, w1, w2, . . . , wn: weights of the vertices (0 ≤ wi ≤ 106).

The next m lines contain a description of Xiuhan’s tuples. Each of these lines contains three integers ai, bi, si (1 ≤ ai, bi ≤ n, ai ≠ bi, 0 ≤ si ≤ 106).

출력

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.

예제 입력 1

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

예제 출력 1

4
2 3 1 4

예제 입력 2

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

예제 출력 2

2
3 5

출처

Camp > Petrozavodsk Programming Camp > Summer 2019 > Day 2 F번

  • 문제를 만든 사람: 300iq