Score : 700 points
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:
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.
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
Print the answer.
4 3 3 1 0 1 2 1 2 10 2 3 20 2 4 50
60
G' will only be connected when Vertex 2 is painted in Color 3.
5 2 4 0 0 0 0 0 1 2 10 2 3 10
-1
Regardless of how Ringo paints the vertices, two edges is not enough to connect four vertices as one.
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