To celebrate being able to reconstruct his array, Max has decided to solve Single Source Shortest Path but wants it to be harder, so he came up with the following problem:

Given a graph of $N$ vertices with $M$ bidirectional-weighted edges and $K$ toggles for the bits for any given edge weight you travel, find the shortest path from $1$ to $N$.

The $i^{\text{th}}$ toggle allows you to set the $p_i^{\text{th}}$ bit to $0$ at most once on any edge weight you travel on from $1$ to $N$.

You can use multiple toggles on the same edge.

What is the minimum cost to travel from $1$ to $N$ using at most $K$ of the toggles?

Constraints

$1\le N\le 20000$

$N-1\le M\le min(50000,\frac{N\times (N-1)}{2})$

$0\le K\le 8$

$0\le p_i\le 10$

$1\le u_i,v_i\le N$

$u_i\ne v_i$

$1\le w_i\le 40000$

The data are generated such that there is always a path of edges from $1$ to $N$.

Note the increased constraints on $K$.

Input Specification

The first line will contain three integers, $N$, $M$, and $K$, the number of vertices, edges, and toggles, respectively.

The next $K$ lines will contain an integer, $p_i$, the $i^{\text{th}}$ toggle that can be used to set the $p_i^{\text{th}}$ bit of any edge weight that is travelled on from $1$ to $N$ to $0$.

The next $M$ lines will contain three integers, $u_i$, $v_i$, and $w_i$, a bidirectional edge from $u_i$ to $v_i$ with a weight of $w_i$.

Output Specification

Output the minimum distance from $1$ to $N$ after using at most $K$ of the toggles.

Sample Input

3 3 3
1
2
3
1 3 1
1 2 2
2 3 12

Sample Output

0

Explanation for Sample

It is optimal to take the path $1\to 2\to 3$ to get a distance of $0$: use $p_1=1$ on the edge from $1$ to $2$, giving a weight of $0$; use $p_2=2$ on the edge from $2$ to $3$, giving a weight of $8$; use $p_3=3$ on the edge from $2$ to $3$ again, giving a weight of $0$.