| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 11 | 0 | 0 | 0.000% |
$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ドル$ 本を選んでグラフに追加する、という操作を任意の回数行うことができる。ただし、どの瞬間においても次の条件が成り立っていなければならない。
すべての頂点を連結にできるか判定せよ。できるならば、グラフに辺を追加していく方法を一つ出力せよ。
入力は以下の形式で標準入力から与えられる。
$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 3 50 50 1 2 100 1 2 101 1 2 102
1 1
3 1 50 50 50 1 2 100
-1
すべての辺をグラフに追加しても、すべての頂点を連結にできない。