Marathon

After weeks of training, William finally found out how to win a marathon: by cheating! He teamed up with a skillful driver, his friend Alessandro, and is planning on driving instead of running.

The marathon takes place in the beautiful city of Pordenone, which is formed by $N$ intersections and $M$ bidirectional roads. Each road is exactly $w_i$ meters long.

The marathon starts at intersection $0$ and ends at intersection $N-1$. Marathoners must go through $K$ checkpoints given in the array $S$, however, they can run through any route between two consecutive checkpoints.

William's plan is the following:

He will run from the starting line to the first checkpoints, then he will sneak into Alessandro's car and reach the second checkpoint, next, he will run another piece to the following checkpoint. After that, he will sneak again into Alessandro's car and reach the following checkpoint and so on until he reach the finishing line.

Since William wants to win the marathon, he will always take the shortest path between two checkpoints. However, while trying to hide the evidence of the cheat, William lost the original arrangement of the checkpoints!

In order to plan for the worst case scenario, William is interested in the maximum distance he will have to run among all the possible checkpoint arrangements. Can you help him?

Input data

The first line of the input contains the integers $N$ and $M$. The second line contains the integer $K$, followed by $K$ integers $S_i$, $K$ even.

Each of the following $M$ lines contains $3$ integers $u$, $v$ and $w$ describing a road of length $w$ connecting intersections $u$ and $v$.

Output data

You will need to write in the output a single integer: the maximum distance that William will have to run among all the possible checkpoint arrangements.

Constraints and clarifications

• $1 \leq N \leq 500$
• $1 \leq M \leq \frac{N \cdot (N-1)}{2}$
• $0 \leq K \leq N-2$, $K$ even.
• $0 \leq u, v \leq N-1$
• $0 \leq w \leq 10^9$
• For tests worth $25$ points, $K$ = $0$.
• For tests worth $35$ more points, $0 \leq K \leq 18$

Example 1

stdin

7 8
2 4 3
0 1 5
0 2 3
1 4 1
2 3 4
1 3 13
4 5 6
1 6 10
5 6 2

stdout

27

Explanation

In the first sample case, the maximum distance is obtained from the arrangement $[4, 3]$:

First, William will run from $0$ to $4$, the shortest path is $0 \rarr 1 \rarr 4$ with length $5 + 1 = 6$;

Then Alessandro will take William to $3$. Finally William will run from $3$ to $6$, the shortest path is $3 \rightarrow 2 \rightarrow 0 \rightarrow 1 \rightarrow 4 \rightarrow 5 \rightarrow 6$ with length $4 + 3 + 5 + 1 + 6 + 2 = 21$.

The total distance is $6 + 21 = 27$.

Example 2

stdin

4 5
0
0 1 4
0 2 2
1 2 0
1 3 6
2 3 9

stdout

8

Explanation

In the second sample case there are no checkpoints, so William must run directly from $0$ to $3$. The shortest path is $0 \rightarrow 2 \rightarrow 1 \rightarrow 3$.