In and Out

The young pirate Will Twister has lost his precious medallion, once given to him by his father. It is now in the hands of Governor Goose. Because the medallion means so much to Will, he decides to steal it back. His presence will not go unnoticed (he is no ninja), so to improve his chances of a clean getaway he will move under the cover of night. That makes the journey to the governor's house dangerous, though, because walking through town at night is suspicious.

Throughout the town, sentries (stationary guards) are posted at strategically chosen junctions. Will is not a good fighter, so he relies on surprise and speed to slip past them. However, if he were to pass the same sentry on both the outbound and the return journey, the element of surprise would be gone the second time and he would risk being caught. Therefore he never wants to pass the same sentry twice.

Will's journey starts and ends at the harbor, where he arrives and departs by boat. He has a map of the town marked with the sentry locations. Since he will be doing a lot of running, he wants the shortest possible round trip to the governor's house and back that does not take him past any sentry more than once. Can you help him find it?

The first line contains a single integer: the number of test cases. Each test case has the following format:

• One line with two integers $N$ and $R$ ($2 \le N \le 1000$, $1 \le R \le 10000$): the number of junctions and the number of roads.
• $R$ lines, each with three integers $a$, $b$ and $l$ ($1 \le a, b \le N$, $1 \le l \le 1000$), meaning there is a bidirectional road of length $l$ between junctions $a$ and $b$.
• One line with one integer $S$ ($0 \le S \le \min(N - 2, 100)$): the number of sentries.
• One line with $S$ distinct integers $s_i$ ($2 \le s_i < N$): the junctions that have a sentry.

The junctions are numbered $1$ through $N$. Will's boat is at junction $1$ and the governor's house is at junction $N$. A path from the boat to the governor's house is guaranteed to exist.

For each test case, output a single line with one integer: the minimum total distance Will must cover for the whole round trip (out to the governor's house and back). If there is no round trip that passes each sentry at most once, output No safe route (without the quotation marks) on its own line instead.