Problem:
 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

Solution (Python):
class Unionfindtree:
    def __init__(self, number):
        self.par = [i for i in range(number)]
        self.rank = [0] * (number)

    def find(self, x):  
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):  
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        else:
            self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connect(self, x, y):  
        return self.find(x) == self.find(y)


N, M, K = map(int, input().split())
C = [int(i) for i in input().split()]
table = []
t = K
for i in range(N):
    if C[i]==0:
        t+=1
        C[i]=t
for i in range(M):
    s, u, c = map(int, input().split())
    a, b = C[s - 1], C[u - 1]
    table.append((c, a, b))

tree = Unionfindtree(t+1)
table.sort()
ct = K - 1
ans = 0
for c, a, b in table:
    if not tree.connect(a, b) and ct > 0:
        tree.union(a, b)
        ans += c
        ct -= 1
if ct > 0:
    print(-1)
else:
    print(ans)