N 個の頂点からなるグラフがある。頂点は 1, 2, ..., N と番号が振られている。i (1 ≤ i ≤ N) 番目の頂点は非負整数の重み a_i をもつ。
はじめ、グラフには辺がない。あなたはグラフに無向辺を追加していくことができる。グラフに追加できる辺の候補は M 本ある。辺は 1, 2, ..., M と番号が振られている。i (1 ≤ i ≤ M) 番目の辺は、頂点 x_i と y_i を端点とし、非負整数の重み z_i をもつ。
あなたの目標は、すべての頂点を連結にすることである。そのために、まだグラフに追加していない辺のうちちょうど 1 本を選んでグラフに追加する、という操作を任意の回数行うことができる。ただし、どの瞬間においても次の条件が成り立っていなければならない。
すべての頂点を連結にできるか判定せよ。できるならば、グラフに辺を追加していく方法を一つ出力せよ。
入力は以下の形式で標準入力から与えられる。
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
とだけ一行に出力せよ。
すべての頂点を連結にできるならば、グラフに辺を追加していく方法を一つ次のように出力せよ。
4 3 50 0 0 50 1 2 0 2 3 100 3 4 0
3 1 3 2
2 番目の辺を追加するのは最後でなければならない。
2 3 50 50 1 2 100 1 2 101 1 2 102
1 1
多重辺が含まれている。
3 1 50 50 50 1 2 100
-1
すべての辺をグラフに追加しても、すべての頂点を連結にできない。