== include(page="template/taskheader" task_id="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?
 

Poveste şi cerinţă...

h2. Date de intrare

The first line of the input file $marathon.in$ 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$.

Fişierul de intrare $marathon.in$ ...

h2. Date de ieşire

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

În fişierul de ieşire $marathon.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 500$
* $1 ≤ M ≤ N * (N-1) / 2$
* $0 ≤ K ≤ N-2$, $K$ even.
* $0 ≤ u, v ≤ N-1$
* $0 ≤ w ≤ 10^9$
* For tests worth $25$ points, $K$ = $0$.
* For tests worth $35$ more points, $0 ≤ K ≤ 18$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. marathon.in |_. marathon.out |

| 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
| 27
|
 
table(example). |_. marathon.in |_. marathon.out |
| 4 5
0
0 1 4
0 2 2
1 2 0
1 3 6
2 3 9
| 8

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

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$ -> $1$ -> $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$ -> $2$ -> $0$ -> $1$ -> $4$ -> $5$ -> $6$ with length $4 + 3 + 5 + 1 + 6 + 2 = 21$.
 
The total distance is $6 + 21 = 27$.
 
In the second sample case there are no checkpoints, so William must run directly from $0$ to $3$. The shortest path is $0$ -> $2$ -> $1$ -> $3$.

...

== include(page="template/taskfooter" task_id="marathon") ==