Shopping

You have just moved into a new apartment and have a long list of items to buy. Buying this many items means visiting many different stores, and you would like to minimize the amount of driving needed to buy everything on your list.

The city is a set of intersections connected by roads. Your house and every store sit at some intersection. Find the length of the shortest route that starts at your house, visits every store you need to shop at, and returns to your house.

The first line contains a single integer, the number of test cases. Each test case begins with a line containing two integers $N$ and $M$, the number of intersections and the number of roads in the city ($1 \le N \le 100000$, $1 \le M \le 100000$). The intersections are numbered from $0$ to $N-1$, and your house is at intersection $0$. Each of the next $M$ lines contains three integers $X$, $Y$, and $D$, meaning that intersections $X$ and $Y$ are connected by a bidirectional road of length $D$. The next line contains a single integer $S$, the number of stores you must visit ($1 \le S \le 10$). Each of the following $S$ lines contains one integer, the intersection at which a store is located. Every store is reachable from your house.

For each test case, output a single line containing one integer: the length of the shortest shopping trip that starts at your house, visits all the stores, and returns to your house.