STATEMENT

You are given a undirected weighed graph and upto 5 vertices. The cost of a subgraph is the sum of the weights of edges in the subgraph. Your task will be to find the cheapest connected subgraph containing these vertices. You have to report the sum of the weight the of edges in this subgraph.

INPUT

The input file will contain several test cases. The first line contains an integer t, the number of test-cases. The succeeding lines contain the test-cases.

Input Format:

Each test-case comprises the following:

Line 1: N M: The number of vertices and edges respectively
Vertices are numbered 1 to N.
M lines: 3 space seperated integers, denoting the endpoints of an edge and its weight.
The last line: The first integer is K, the size of the subset of the vertices. K integers follow denoting the number of the vertices in the subset. The numbers are space seperated.

OUTPUT

The output should comprise the solutions to all the test cases, in the order of the test cases in the input. There should NOT be any blank line in the output.

Output Format:

Line 1: An integer, the weight of edges in the cheapest connected subgraph.

POINTS and CONSTRAINTS

Total points: 100

Easy set (20 points ) 5 ≤ N ≤ 20 , 10 ≤ M ≤ 200
Hard set (80 points ) 5 ≤ N ≤ 120 , 10 ≤ M ≤ 5000
Time Limit: 5 seconds
Memory Limit: 64 MB (Stack memory: 8MB)

SAMPLE INPUT

1
4 6
1 2 24
1 3 79
1 4 43
2 3 76
2 4 86
3 4 81
3 1 2 3

SAMPLE OUTPUT

100