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 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 $S[0], S[1] ... S[K-1]$, however, they can run through any route between two consecutive checkpoints.

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:

* $1 ≤ N ≤ 500$
* $1 ≤ M ≤ N * (N-1) / 2$
* $0 ≤ K ≤ N-2$, $K$ even.

* $0 &le u, v ≤ N-1$

* $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$

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

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

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") ==