Connection

Time limit2sMemory limit512 MB

Summary

Decide whether all N vertices can be connected by adding candidate edges while every component keeps its vertex weight sum at least its edge weight sum, and print the edge order.

Level: Medium7 of 10
Topics: Union-find, Greedy, Sorting
Solved: No attempts yet

Problem

There is a graph with $N$ vertices numbered $1, 2, \ldots, N$ . Vertex $i$ ( $1 \leq i \leq N$ ) has a non-negative integer weight $a_i$ .

Initially, the graph has no edges. You may add undirected edges to the graph. There are $M$ candidate edges, numbered $1, 2, \ldots, M$ . Edge $i$ ( $1 \leq i \leq M$ ) connects vertices $x_i$ and $y_i$ and has a non-negative integer weight $z_i$ .

Your goal is to make all vertices connected. To do so, you may repeat the following operation any number of times: choose exactly one candidate edge that has not been added yet and add it to the graph. At every moment, the following condition must hold.

For every connected component of the graph, (sum of vertex weights) $\geq$ (sum of edge weights).

Determine whether all vertices can be connected.

Input

$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$

Output

If it is impossible to connect all vertices, print -1 on a single line.

If it is possible, print one way to add edges as follows.

On the first line, print the number $m$ of edges to add ( $1 \leq m \leq M$ ).
On each of the next $m$ lines, the $k$ -th line contains the number $i_k$ ( $1 \leq i_k \leq M$ ) of the $k$ -th edge to add.

Constraints

$2 \leq N \leq 10^5$
$a_i$ is an integer, $0 \leq a_i \leq 10^9$
$1 \leq M \leq 10^5$
$1 \leq x_i < y_i \leq N$
$z_i$ is an integer, $0 \leq z_i \leq 10^9$

Examples3

Example 1

Input

Expected output

Example 2
Input
```
2 3
50 50
1 2 100
1 2 101
1 2 102
```
Expected output
```
1
1
```
Example 3
Input
```
3 1
50 50 50
1 2 100
```
Expected output
```
-1
```