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

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

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