分数: 700 点
问题陈述
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 是由边连接的两个顶点的颜色 i in G.
- 添加长度为 的边 w_i 连接顶点 x 和 y in G'.
的最小生成树中边的长度的最小可能总和是多少 G'?如果 G' 无论Ringo如何绘制顶点都不会连接,打印 -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
G' 仅当 Vertex 时才会连接 2 涂有颜色 3.
示例输入 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