Colorful MST

### 题目描述 无向图 $G$ 有 $N$ 个顶点和 $M$ 条边。顶点的编号为 $1$ 到 $N$，第 $i$ 条边连接点 $a_i$ 和点 $b_i$，长度为 $w_i$。 有 $K$ 种颜色，编号 $1$ 到 $K$。图 $G$ 中的一些点已经被染了这 $K$ 种颜色中的某一种，还有一些点没有被染色。点 $i$ 染的颜色用 $c_i$ 表示，当 $c_i=0$ 时，点 $i$ 未被染色。 你需要把 $G$ 中未被染色的点也染上这 $K$ 种颜色，每个点染一种。染完后，按照下面的方法构造无向图 $G'$： - 画 $K$ 个顶点，编号 $1$ 到 $K$。 - 画 $M$ 条边，第 $i$ 条边连接的两个点的编号为图 $G$ 中第 $i$ 条边所连接的两个点的颜色编号，长度与图 $G$ 中第 $i$ 条边的长度一致。 若 $G'$ 可连通，求出其最小生成树大小；否则，输出 $-1$。 ### 输入格式 第一行输入三个整数 $N,M,K$。 第二行输入 $N$ 个整数，表示数列 $c$。 接下来 $M$ 行，每行输入三个整数 $a_i,b_i,w_i$，表示图 $G$ 中第 $i$ 条边的信息。 ### 输出格式 一行一个整数。 ### 说明/提示 #### 样例 #1 解释 当且仅当点 $2$ 染上颜色 $3$ 时，图 $G'$ 连通。 #### 样例 #2 解释 无论怎么染色，两条边是不可能使四个点连通的。 #### 数据规模与约定 对于全部测试点，保证： - $1\le N,M\le 10^5$，$1\le K\le N$； - $0\le c_i\le K$，$1\le a_i,b_i\le N$，$1\le w_i\le 10^9$。 **不保证** 给定的图 $G$ 连通，没有重边或自环。 #### 子任务 本题在 AT 上满分 $700$。AT 采取捆绑测试。 - 对于前 $100$ 分的测试数据，保证 $N=K$ 且 $c_i=i$； - 对于另外 $100$ 分的数据，保证 $c_i\neq 0$； - 对于另外 $200$ 分的数据，保证 $c_i=0$； - 对于剩余的数据，无特殊限制。

[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 $

答えを出力せよ。

4 3 3
1 0 1 2
1 2 10
2 3 20
2 4 50

60

5 2 4
0 0 0 0 0
1 2 10
2 3 10

-1

9 12 9
1 2 3 4 5 6 7 8 9
6 9 9
8 9 6
6 7 85
9 5 545631016
2 1 321545
1 6 33562944
7 3 84946329
9 7 15926167
4 7 53386480
5 8 70476
4 6 4549
4 8 8

118901402

18 37 12
5 0 4 10 8 7 2 10 6 0 9 12 12 11 11 11 0 1
17 1 1
11 16 7575
11 15 9
10 10 289938980
5 10 17376
18 4 1866625
8 11 959154208
18 13 200
16 13 2
2 7 982223
12 12 9331
13 12 8861390
14 13 743
2 10 162440
2 4 981849
7 9 1
14 17 2800
2 7 7225452
3 7 85
5 17 4
2 13 1
10 3 45
1 15 973
14 7 56553306
16 17 70476
7 18 9
9 13 27911
18 14 7788322
11 11 8925
9 13 654295
2 10 9
10 1 545631016
3 4 5
17 12 1929
2 11 57
1 5 4
1 17 7807368

171

### 制約 - $ 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 $ つの頂点が連結になるようにすることはできません。