A - Colorful MST 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 700 点

問題文

りんごさんは頂点に 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 を出力してください。

制約

  • 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 が成立する

入力

入力は以下の形式で標準入力から与えられる。

N M K
c_1 c_2 ... c_{N}
a_1 b_1 w_1
:
a_M b_M w_M

出力

答えを出力せよ。

入力例 1

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

出力例 1

60

頂点 2 に色 3 を塗ったときのみ、G' が連結になります。

入力例 2

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

出力例 2

-1

どのようにりんごさんが色を塗っても、2 本の辺で 4 つの頂点が連結になるようにすることはできません。

入力例 3

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

出力例 3

118901402

入力例 4

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

出力例 4

171

Score : 700 points

Problem Statement

Ringo has an undirected graph G with N vertices numbered 1,2,...,N and M edges numbered 1,2,...,M. Edge i connects Vertex a_{i} and b_{i} and has a length of w_i.

Now, he is in the middle of painting these N vertices in K colors numbered 1,2,...,K. Vertex i is already painted in Color c_i, except when c_i = 0, in which case Vertex i is not yet painted.

After he paints each vertex that is not yet painted in one of the K colors, he will give G to Snuke.

Based on G, Snuke will make another undirected graph G' with K vertices numbered 1,2,...,K and M edges. Initially, there is no edge in G'. The i-th edge will be added as follows:

  • Let x and y be the colors of the two vertices connected by Edge i in G.
  • Add an edge of length w_i connecting Vertex x and y in G'.

What is the minimum possible sum of the lengths of the edges in the minimum spanning tree of G'? If G' will not be connected regardless of how Ringo paints the vertices, print -1.

Constraints

  • 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}
  • The given graph may NOT be simple or connected.
  • All input values are integers.

Partial Scores

  • In the test set worth 100 points, N = K and c_i = i.
  • In the test set worth another 100 points, c_i \neq 0.
  • In the test set worth another 200 points, c_i = 0.

Input

Input is given from Standard Input in the following format:

N M K
c_1 c_2 ... c_{N}
a_1 b_1 w_1
:
a_M b_M w_M

Output

Print the answer.

Sample Input 1

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

Sample Output 1

60

G' will only be connected when Vertex 2 is painted in Color 3.

Sample Input 2

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

Sample Output 2

-1

Regardless of how Ringo paints the vertices, two edges is not enough to connect four vertices as one.

Sample Input 3

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

Sample Output 3

118901402

Sample Input 4

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

Sample Output 4

171