Connection

Time Limit : 2 sec, Memory Limit : 262144 KB

Now judge is temporally not available for this problem. We are earnestly making necessary data. Sorry for the inconvenience.

J - 連結

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

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

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

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

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

Constraints

  • 2 ≤ N ≤ 10^5
  • a_i は整数,0 ≤ a_i ≤ 10^9
  • 1 ≤ M ≤ 10^5
  • 1 ≤ x_i<y_i ≤ N
  • z_i は整数,0 ≤ z_i ≤ 10^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 ≤ m ≤ M) を出力せよ。
  • 2 行目からの m 行のうち k 行目には、k 番目にグラフに追加する辺の番号 i_k (1 ≤ i_k ≤ 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

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


Source: ACM-ICPC Japan Alumni Group Summer Camp 2015 , Day 2, Tokyo, Japan, 2015-09-12
http://acm-icpc.aitea.net/
http://jag2015summer-day2.contest.atcoder.jp/