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 20\,000~

~N-1 \le M \le \min(50\,000, \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 40\,000~

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~.