Problem Description

Ringo-san has an undirected graph \( G \) consisting of \( N \) vertices numbered \( 1, 2, ..., N \) and \( M \) edges numbered \( 1, 2, ..., M \). Edge \( i \) connects vertices \( a_i \) and \( b_i \) bidirectionally with a length of \( w_i \).

Currently, Ringo-san is in the process of coloring these \( N \) vertices with \( K \) types of colors numbered \( 1, 2, ..., K \). Vertex \( i \) is painted with color \( c_i \). However, if \( c_i = 0 \), vertex \( i \) is not yet colored.

Ringo-san will color all uncolored vertices with one of the \( K \) types of colors and then give \( G \) to Snuke-kun.

Snuke-kun will use \( G \) to create an undirected graph \( G' \) consisting of \( K \) vertices numbered \( 1, 2, ..., K \) and \( M \) edges. Initially, \( G' \) has no edges. Edge \( i \) is added to \( G' \) as follows:

• When focusing on edge \( i \) of \( G \), let the colors painted on the vertices at both ends be \( x \) and \( y \) respectively.
• Add an edge of length \( w_i \) connecting vertices \( x \) and \( y \) bidirectionally to \( G' \).

What is the minimum possible sum of the lengths of the edges included in the minimum spanning tree of \( G' \)? Output \( -1 \) if \( G' \) cannot be connected regardless of how Ringo-san colors the vertices.

Input Format

The input is given from the 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 Format

Output the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

60

Sample Input #2

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

Sample Output #2

-1

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

Notes/Hints

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 given inputs are integers.

Partial Points

• For a dataset worth 100 points, \( N = K \) and \( c_i = i \) hold.
• For another dataset worth 100 points, \( c_i \neq 0 \) holds.
• For another dataset worth 200 points, \( c_i = 0 \) holds.

Sample Explanation 1

Only when vertex \( 2 \) is colored with color \( 3 \), \( G' \) becomes connected.

Sample Explanation 2

No matter how Ringo-san colors the vertices, it is impossible to connect 4 vertices with only 2 edges.

见题面 Input 部分

见题面 Output 部分