AT_asaporo2_a Colorful MST

[problemUrl]: https://atcoder.jp/contests/cf17-tournament-round2-open/tasks/asaporo2_a りんごさんは頂点に $ 1,2,...,N $ の番号がついた $ N $ 個の頂点と $ 1,2,...,M $ の番号がついた $ M $ 本の辺からなる無向グラフ $ G $ を持っています。 辺 $ i $ は頂点 $ a_{i} $ と $ b_{i} $ を双方向につなぐ長さ $ w_i $ の辺です。 現在、りんごさんはこれらの $ N $ 個の頂点を $ 1,2,...,K $ の番号がついた $ K $ 種類の色で彩色している途中です。頂点 $ i $ は色 $ c_i $ で塗られています。ただし、$ c_i\ =\ 0 $ ならば頂点 $ i $ にはまだ色が塗られていません。 りんごさんはまだ色が塗られていない全ての頂点を $ K $ 種類の色のいずれかでそれぞれ塗ったのち、すぬけくんに $ G $ をあげます。 すぬけくんは $ G $ を使って頂点に $ 1,2,...,K $ の番号がついた $ K $ 個の頂点と $ M $ 本の辺からなる無向グラフ $ G' $ を作ります。 はじめ、$ G' $ には辺がありません。$ i $ 番目の辺は以下のようにして追加されます。 - $ G $ の辺 $ i $ に着目したとき両端の頂点に塗られている色をそれぞれ $ x,y $ とする - 頂点 $ x $ と $ y $ を双方向につなぐ長さ $ w_i $ の辺を $ G' $ に追加する $ G' $ の最小全域木に含まれる辺の長さの総和としてありうる値は最小でいくつになりますか？りんごさんがどのように色を塗っても $ G' $ が連結にならない場合は $ -1 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ c_1 $ $ c_2 $ $ ... $ $ c_{N} $ $ a_1 $ $ b_1 $ $ w_1 $ $ : $ $ a_M $ $ b_M $ $ w_M $

答えを出力せよ。

### 制約 - $ 1\ \leq\ N,M\ \leq\ 10^{5} $ - $ 1\ \leq\ K\ \leq\ N $ - $ 0\ \leq\ c_i\ \leq\ K $ - $ 1\ \leq\ a_i,b_i\ \leq\ N $ - $ 1\ \leq\ w_i\ \leq\ 10^{9} $ - 与えられるグラフは単純とも連結とも限らない - 与えられる入力は全て整数 ### 部分点 - $ 100 $ 点分のデータセットでは $ N=K,c_i\ =\ i $ が成立する - 別の $ 100 $ 点分のデータセットでは $ c_i\ \neq\ 0 $ が成立する - 別の $ 200 $ 点分のデータセットでは $ c_i\ =\ 0 $ が成立する ### Sample Explanation 1 頂点 $ 2 $ に色 $ 3 $ を塗ったときのみ、$ G' $ が連結になります。 ### Sample Explanation 2 どのようにりんごさんが色を塗っても、$ 2 $ 本の辺で $ 4 $ つの頂点が連結になるようにすることはできません。