Note

The execution time limit for this problem is $\boldsymbol{ \textcolor {red} {5.0} }$ seconds per $1$ test case.

Problem Statement

Mt. Hakkou has $N$ locations numbered $1, 2, \dots, N$,
and these locations are connected by $M$ bidirectional roads numbered $1, 2, \dots, M$.

Road $i$ $(1 \leq i \leq M)$ connects location $A_{i}$ and location $B_{i}$, and the distance between them is $C_{i}$.

Koa commutes from her home at location $1$ on this mountain to Koume Academy at location $N$,
and on the way, it is her daily routine to pet all the wild boars living on the $K$ roads $R_{1},R_{2},\dots,R_{K}$.

Suppose Koa chooses her route from her home to Koume Academy so that it passes through every one of the roads $R_{1},R_{2},\dots,R_{K}$ at least $1$ time,
and so that the total distance of the entire route is minimized. Find that travel distance.

Note that she may pass through the same road $2$ or more times, and she may visit location $N$ $2$ or more times.

Constraints

• $ 2 \leq N \leq 10^{4} $

• $\displaystyle N-1 \leq M \leq \min \left( 2 \times 10^{4}, \frac{N \times (N-1) }{2} \right)$

• $1 \leq K \leq \min (12,M)$

• $1 \leq R_{i} \leq M$ $(1 \leq i \leq K)$

• $R_{i} \neq R_{j}$ $(1 \leq i < j \leq K)$

• $1 \leq A_{i},B_{i} \leq N$ and $A_{i} \neq B_{i}$ $(1 \leq i \leq M)$

• $(A_{i},B_{i}) \neq (A_{j},B_{j})$ and $(A_{i},B_{i}) \neq (B_{j},A_{j})$ $(1 \leq i < j \leq M)$

• $1 \leq C_{i} \leq 10^{4}$ $(1 \leq i \leq M)$

• Between any $2$ locations, it is possible to travel by passing through $1$ or more roads.

• All input values are integers.

Input

The input is given in the following format.

$N$ $M$ $K$
$R_{1}$ $R_{2}$ $\cdots$ $R_{K}$
$A_{1}$ $B_{1}$ $C_{1}$
$A_{2}$ $B_{2}$ $C_{2}$
     $\vdots$
$A_{M}$ $B_{M}$ $C_{M}$

• Line $1$ contains $N$, $M$, and $K$ in this order, separated by single spaces.

• Line $2$ contains $R_{1},R_{2},\dots,R_{K}$ in this order, separated by single spaces.

• Line $(2+i)$ $(1 \leq i \leq M)$ contains $A_{i}$, $B_{i}$, and $C_{i}$ in this order, separated by single spaces.

Output

Output the answer on $1$ line, followed by a newline.

Sample

5 6 2
3 4
1 2 3
1 3 1
2 3 10
3 4 20
3 5 5
4 5 7

40

4 6 3
2 3 4
1 2 4
1 3 6
1 4 1
2 3 3
2 4 2
3 4 1

13

6 6 6
2 4 6 1 3 5
1 2 1
3 1 2
4 2 3
2 5 4
3 4 5
6 5 6

22

10 20 12
13 10 6 19 14 12 16 4 3 17 2 9
5 8 43
4 7 3
6 7 1853
2 7 1
6 5 1
4 3 7153
10 4 108
9 5 32
10 1 8
3 2 45
6 1 5281
6 9 7331
1 8 19
10 5 78
6 4 4
9 1 147
1 3 2
7 9 21
10 9 36
3 9 8887

16742