連結

$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(辺の重みの総和)$ である。

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

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

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

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

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

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

• $2\leq N\leq10^5$
• $a\_i$ は整数，$0\leq a\_i\leq10^9$
• $1\leq M\leq10^5$
• $1\leq x\_i < y\_i \le N$
• $z\_i$ は整数，$0\leq z\_i\leq10^9$