CF2222F.Building Tree

Shall We Talk (Tre Lune MMXIX)

Exber has an undirected graph with $ n $ vertices and $ m $ edges. The $ i $ -th edge connects vertices $ u_i $ and $ v_i $ and has weight $ w_i $ .

For every path, let the weights of the edges in it form a set $ S $ ; then the length of this path is defined as $ \operatorname{mex}(S) $ . Here, $ \operatorname{mex}(S) $ denotes the minimum excluded (MEX) $ ^{\text{∗}} $ of the collection $ S $ . Let $ \mathrm{dis}(u,v) $ denote the minimum path length among all paths starting at $ u $ and ending at $ v $ .

Now, Exber wants to construct a new graph with $ q $ vertices. In the new graph, the color of the $ i $ -th vertex is $ c_i $ . Initially, there are no edges in this graph. If Exber adds an edge connecting vertex $ u $ and vertex $ v $ , it will cost $ \mathrm{dis}(c_u,c_v) $ time. If vertex $ c_u $ and vertex $ c_v $ are not connected in the given graph, Exber can not add an edge connecting vertex $ u $ and vertex $ v $ in the new graph.

Determine the minimum amount of time Exber needs to spend to make the new graph connected.

$ ^{\text{∗}} $ The minimum excluded (MEX) of a collection of integers $ S_1, S_2, \ldots, S_k $ is defined as the smallest non-negative integer $ x $ which does not occur in the collection $ S $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains three integers $ n $ , $ m $ , and $ q $ ( $ 1\le n,m\le 3\cdot 10^5 $ , $ 1\le q\le n $ ) — the number of nodes in the graph, the number of edges in the graph, and the number of nodes in the new graph, respectively.

The next $ m $ lines each contain three integers $ u $ , $ v $ , and $ w $ ( $ 1\le u,v\le n $ , $ 0\le w\le m $ ), indicating that there is an edge of weight $ w $ between vertices $ u $ and $ v $ .

The next line contains $ q $ integers $ c_i $ ( $ 1\le c_i\le n $ ), indicating that the color of vertex $ i $ in the new graph is $ c_i $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3\cdot 10^5 $ .

It is guaranteed that the sum of $ m $ over all test cases does not exceed $ 3\cdot 10^5 $ .

It is guaranteed that the sum of $ q $ over all test cases does not exceed $ 3\cdot 10^5 $ .

For each test case, output a single integer — the minimum amount of time Exber needs to spend to make the new graph connected. If it is impossible, output $ -1 $ .

In the first test case, the original graph has $ 5 $ vertices and $ 5 $ edges. The colors of the vertices in the new graph are $ 1 $ , $ 2 $ , and $ 4 $ .

The original graph of the first test case. The numbers inside the brackets represent the indices of the vertices in the new graph whose color is the index of this vertex in the original graph.In the new graph, Exber will add edges $ (1,2) $ and $ (2,3) $ , and the first edge will cost him $ 1 $ time and the second edge will cost him $ 0 $ time; therefore, the total time is $ 1 $ .

In the second test case, the original graph has $ 10 $ vertices and $ 12 $ edges. The colors of the vertices in the new graph are $ 3 $ , $ 5 $ , $ 9 $ , $ 10 $ , and $ 6 $ .

The original graph of the second test case. The numbers inside the brackets represent the indices of the vertices in the new graph whose color is the index of this vertex in the original graph.In the new graph, Exber will add edges $ (1,2) $ , $ (2,3) $ , $ (3,4) $ , and $ (4,5) $ , and each edge will cost him $ 1 $ time; therefore, the total time is $ 4 $ .