Japan Alumni Group Summer Camp 2015 Day 2

J - 連結


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

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

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


Submit提出する