405083: GYM101778 D Help Conan

Conan is tired of his current job, so he decided to get a new job and applied for an engineering position in one of the largest technology companies in the Silicon Valley. Conan is currently in the last interview. Unfortunately, this interview is very tough, so that Conan is currently struggling with a very hard question!

Conan is given an undirected connected graph of n nodes and m edges. This graph has a special property where it contains k important nodes. Conan task is to find a sub-graph in the given graph such that it contains all the important nodes (but may include additional unimportant nodes) such that its length is as minimal as possible. The length of a sub-graph is defined to be the sum of the lengths of all its edges.

Conan has no idea how he can solve this question, but he is determined not to return to his previous job. Therefore, Conan used his special gadgets to leak the question to you so that you can help him. Conan will give you his first salary if you helped him. Can you?

The first line contains an integer T (1 ≤ T ≤ 150), where T is the number of test cases.

The first line of each test case contains three integers n, m, and k (2 ≤ n ≤ 15) () (1 ≤ k ≤ n), where n is the number of nodes, m is the number of edges, and k is the number of important nodes.

Then m lines follow, each line contains three integers u, v, and c (1 ≤ u, v ≤ n) (0 ≤ c ≤ 10⁶), giving an edge of length c between nodes u and v. It is guaranteed that there are no self-loops and multiple edges.

Then a line follows containing k distinct integers x₁, x₂, ..., x_k (1 ≤ x_i ≤ n), giving the indices of the important nodes. Nodes are numbed from 1 to n.

For each test case, print a single line containing the minimum length of a sub-graph in the given graph such that it contains all the important nodes (but may include additional unimportant nodes)

3
3 3 3
1 2 3
1 3 7
2 3 5
1 2 3
3 3 3
1 2 3
1 3 3
2 3 5
1 2 3
3 3 2
1 2 3
1 3 7
2 3 2
1 3

8
6
5