Problem Statement

$N$ 個の頂点からなるグラフがある。頂点は $1,\\ 2,\\ ...,\\ N$ と番号が振られている。$i$ ($1\\leq i\\leq N$) 番目の頂点は非負整数の重み $a_i$ をもつ。

はじめ、グラフには辺がない。あなたはグラフに無向辺を追加していくことができる。グラフに追加できる辺の候補は $M$ 本ある。辺は $1,\\ 2,\\ ...,\\ M$ と番号が振られている。$i$ ($1\\leq i\\leq M$) 番目の辺は、頂点 $x_i$ と $y_i$ を端点とし、非負整数の重み $z_i$ をもつ。

あなたの目標は、すべての頂点を連結にすることである。そのために、まだグラフに追加していない辺のうちちょうど $1$ 本を選んでグラフに追加する、という操作を任意の回数行うことができる。ただし、どの瞬間においても次の条件が成り立っていなければならない。

• グラフのどの連結成分についても、$(頂点の重みの総和)\\geq(辺の重みの総和)$ である。

すべての頂点を連結にできるか判定せよ。できるならば、グラフに辺を追加していく方法を一つ出力せよ。

Constraints

• $2\\leq N\\leq10^5$
• $a_i$ は整数，$0\\leq a_i\\leq10^9$
• $1\\leq M\\leq10^5$
• $1\\leq x_i<y_i\\leq N$
• $z_i$ は整数，$0\\leq z_i\\leq10^9$

Input Format

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_1$ $a_2$ $...$ $a_N$ $x_1$ $y_1$ $z_1$ $x_2$ $y_2$ $z_2$ $:$ $x_M$ $y_M$ $z_M$

Output Format

すべての頂点を連結にできないならば、-1 とだけ一行に出力せよ。

すべての頂点を連結にできるならば、グラフに辺を追加していく方法を一つ次のように出力せよ。

• $1$ 行目には、グラフに追加する辺の本数 $m$ ($1\\leq m\\leq M$) を出力せよ。
• $2$ 行目からの $m$ 行のうち $k$ 行目には、$k$ 番目にグラフに追加する辺の番号 $i_k$ ($1\\leq i_k\\leq M$) を出力せよ。

Sample Input 1

4 3
50 0 0 50
1 2 0
2 3 100
3 4 0

Sample Output 1

3
1
3
2

$2$ 番目の辺を追加するのは最後でなければならない。

Sample Input 2

2 3
50 50
1 2 100
1 2 101
1 2 102

Sample Output 2

1
1

多重辺が含まれている。

Sample Input 3

3 1
50 50 50
1 2 100

Sample Output 3

-1

すべての辺をグラフに追加しても、すべての頂点を連結にできない。