22419번 - 連結 스페셜 저지다국어

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