연결

시간 제한2초메모리 제한512 MB

요약

각 연결 요소의 정점 가중치 합이 간선 가중치 합 이상을 유지하도록 후보 간선을 추가해 모든 정점을 연결할 수 있는지 판단하고, 추가할 간선의 순서를 출력합니다.

난이도: 보통10점 중 7점
유형: 유니온 파인드, 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

$N$ 개의 정점으로 이루어진 그래프가 있다. 정점에는 $1, 2, \ldots, N$ 번호가 붙어 있다. $i$ ( $1 \leq i \leq N$ )번째 정점은 음이 아닌 정수 가중치 $a_i$ 를 가진다.

처음에는 그래프에 간선이 없다. 그래프에 무향 간선을 추가할 수 있다. 추가할 수 있는 간선 후보는 $M$ 개이다. 간선에는 $1, 2, \ldots, M$ 번호가 붙어 있다. $i$ ( $1 \leq i \leq M$ )번째 간선은 정점 $x_i$ 와 $y_i$ 를 양 끝점으로 하고, 음이 아닌 정수 가중치 $z_i$ 를 가진다.

목표는 모든 정점을 연결하는 것이다. 이를 위해 아직 추가되지 않은 간선 중 정확히 1개를 골라 그래프에 추가하는 연산을 원하는 만큼 반복할 수 있다. 단, 어느 순간에도 다음 조건이 성립해야 한다.

그래프의 어느 연결 요소에 대해서도, (정점 가중치의 합) $\geq$ (간선 가중치의 합)이다.

모든 정점을 연결할 수 있는지 판정한다.

입력

$N$ $M$

$a_1$ $a_2$ $\ldots$ $a_N$

$x_1$ $y_1$ $z_1$

$x_2$ $y_2$ $z_2$

$:$

$x_M$ $y_M$ $z_M$

출력

모든 정점을 연결할 수 없으면 -1만 한 줄에 출력한다.

모든 정점을 연결할 수 있으면 간선을 추가하는 방법 하나를 다음과 같이 출력한다.

첫 줄에 추가할 간선의 수 $m$ ( $1 \leq m \leq M$ )을 출력한다.
다음 $m$ 개 줄의 $k$ 번째 줄에는 $k$ 번째로 추가할 간선의 번호 $i_k$ ( $1 \leq i_k \leq M$ )를 출력한다.

제한

$2 \leq N \leq 10^5$
$a_i$ 는 정수이고, $0 \leq a_i \leq 10^9$
$1 \leq M \leq 10^5$
$1 \leq x_i < y_i \leq N$
$z_i$ 는 정수이고, $0 \leq z_i \leq 10^9$

예제3

예제 1

입력

예상 출력

예제 2
입력
```
2 3
50 50
1 2 100
1 2 101
1 2 102
```
예상 출력
```
1
1
```
예제 3
입력
```
3 1
50 50 50
1 2 100
```
예상 출력
```
-1
```