问题陈述

Ringo有一个无向图$G$，其中$N$个顶点编号为$1,2,...,N$，$M$条边编号为$1,2,...,M$。边$i$连接顶点$a_{i}$和$b_{i}$，长度为$w_i$。

现在，他正在涂这$N$个顶点中的$K$种颜色，编号为$1,2,...,K$。顶点$i$已经被涂上颜色$c_i$，除非$c_i=0$，此时顶点$i$还没有被涂色。

在他将所有未被涂色的顶点之一涂上$K$种颜色之后，他将把$G$交给Snuke。

根据$G$，Snuke将构建另一个无向图$G'$，有$K$个顶点编号为$1,2,...,K$和$M$条边。最初，$G'$中没有边。第$i$条边将按照以下方式添加：

• 设$x$和$y$是由$G$中边$i$连接的两个顶点的颜色。
• 在$G'$中增加一条长度为$w_i$的边，连接顶点$x$和$y$。

求$G'$的最小生成树的边长度之和的最小可能值。如果无论Ringo如何涂色，$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

无论Ringo如何涂色，两条边都不足以连接四个顶点。

样例输入 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