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

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.

Examples

Input

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


Output

60


Input

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


Output

-1


Input

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


Output

118901402


Input

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


Output

171

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringJoiner;
import java.util.StringTokenizer;
import java.util.function.Function;

public class Main {

    static int N, M, K;
    static int[] C;
    static int[] A, B, W;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();
        C = sc.nextIntArray(N);
        A = new int[M];
        B = new int[M];
        W = new int[M];
        for (int i = 0; i < M; i++) {
            A[i] = sc.nextInt()-1;
            B[i] = sc.nextInt()-1;
            W[i] = sc.nextInt();
        }

        System.out.println(solve());
    }

    static long solve() {
        int c = K+1;
        for (int i = 0; i < N; i++) {
            if( C[i] == 0 ) C[i] = c++;
        }

        Edge[] E = new Edge[M];
        for (int i = 0; i < M; i++) {
            E[i] = new Edge(C[A[i]], C[B[i]], W[i]);
        }

        Arrays.sort(E, Comparator.comparingInt(e -> e.w));

        UnionFind uf = new UnionFind(c+10);
        long ans = 0;
        int cnt = 0;
        for (Edge e : E) {
            if( !uf.isSame(e.a, e.b) ) {
                ans += e.w;
                uf.unite(e.a, e.b);
                cnt++;
            }
            if( cnt == K-1 ) break;
        }
        return cnt == K-1 ? ans : -1;
    }

    static class UnionFind {

        private final int[] parent;
        private final int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int root(int i) {
            if( parent[i] == i ) {
                return i;
            } else {
                return parent[i] = root(parent[i]);
            }
        }

        public void unite(int i, int j) {
            int ri = root(i);
            int rj = root(j);
            if( ri == rj ) return;

            if( rank[ri] < rank[rj] ) {
                parent[ri] = rj;

            } else {
                parent[rj] = ri;
                if( rank[ri] == rank[rj] ) {
                    rank[ri]++;
                }
            }
        }

        public boolean isSame(int a, int b) {
            return root(a) == root(b);
        }
    }

    static class Edge {
        final int a, b, w;

        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }

        int opposite(int x) {
            return a == x ? b : a;
        }
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        int[] nextIntArray(int n, int delta) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt() + delta;
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }

    static <A> void writeLines(A[] as, Function<A, String> f) {
        PrintWriter pw = new PrintWriter(System.out);
        for (A a : as) {
            pw.println(f.apply(a));
        }
        pw.flush();
    }

    static void writeLines(int[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int a : as) pw.println(a);
        pw.flush();
    }

    static void writeLines(long[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (long a : as) pw.println(a);
        pw.flush();
    }

    static int max(int... as) {
        int max = Integer.MIN_VALUE;
        for (int a : as) max = Math.max(a, max);
        return max;
    }

    static int min(int... as) {
        int min = Integer.MAX_VALUE;
        for (int a : as) min = Math.min(a, min);
        return min;
    }

    static void debug(Object... args) {
        StringJoiner j = new StringJoiner(" ");
        for (Object arg : args) {
            if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
            else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
            else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
            else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
            else j.add(arg.toString());
        }
        System.err.println(j.toString());
    }
}