CF2222F Building Tree

[Shall We Talk (Tre Lune MMXIX)](https://www.youtube.com/watch?v=NzAIFGFZzV8) Exber 有一个无向图，共有 $n$ 个顶点和 $m$ 条边。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，边权为 $w_i$。 对于每一条路径，设路径中所有边的权值构成集合 $S$，则该路径的长度定义为 $\operatorname{mex}(S)$。这里，$\operatorname{mex}(S)$ 表示集合 $S$ 的最小未包含非负整数（MEX）$^*$。记 $\mathrm{dis}(u,v)$ 为所有从 $u$ 到 $v$ 的路径中最小的路径长度。 现在，Exber 想要构造一个新图，这个新图有 $q$ 个顶点。第 $i$ 个顶点的颜色为 $c_i$。初始时新图没有任何边。如果 Exber 在新图中加入一条连接顶点 $u$ 和顶点 $v$ 的边，则需要花费 $\mathrm{dis}(c_u,c_v)$ 的时间。如果原图中 $c_u$ 和 $c_v$ 不连通，则无法在新图中加入这条边。 请你求出使新图连通所需的最小时间总和。如果无法使新图连通，输出 $-1$。 $^*$ 集合 $S_1, S_2, \ldots, S_k$ 的最小未包含值（MEX）定义为最小的非负整数 $x$，使得 $x$ 不在集合 $S$ 中。

每组数据包含多组测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 10^4$）。接下来是每组测试用例的描述。 每个测试用例第一行为三个整数 $n$、$m$ 和 $q$（$1\le n, m\le 3\cdot 10^5$，$1\le q\le n$），分别表示原图的顶点数、边数，以及新图的顶点数。 接下来 $m$ 行，每行三个整数 $u$、$v$、$w$（$1\le u,v\le n$，$0\le w\le m$），表示原图中有一条连接顶点 $u$ 和 $v$ 且权值为 $w$ 的边。 接下来一行包含 $q$ 个整数 $c_i$（$1\le c_i\le n$），表示新图第 $i$ 个顶点的颜色为 $c_i$。 保证所有测试用例中 $n$ 之和不超过 $3\cdot 10^5$，$m$ 之和不超过 $3\cdot 10^5$，$q$ 之和不超过 $3\cdot 10^5$。

对于每组测试用例，输出一行一个整数，表示使新图连通所需的最小总时间。如果无法连通，输出 $-1$。

在第一个测试用例中，原图包含 $5$ 个顶点和 $5$ 条边。新图中各顶点的颜色为 $1$、$2$ 和 $4$。  第一组数据的原图，括号内的数字表示新图中顶点对应的原图顶点编号。在新图中，Exber 会加入 $(1,2)$ 和 $(2,3)$ 两条边，第一条边的花费为 $1$，第二条边的花费为 $0$，因此总花费为 $1$。 在第二个测试用例中，原图有 $10$ 个顶点和 $12$ 条边。新图中各顶点的颜色分别是 $3$、$5$、$9$、$10$ 和 $6$。  第二组数据的原图，括号内的数字表示新图中顶点对应的原图顶点编号。在新图中，Exber 会加入 $(1,2)$、$(2,3)$、$(3,4)$ 和 $(4,5)$ 四条边，每条边的花费都为 $1$，所以总花费为 $4$。 由 ChatGPT 5 翻译