Note

This problem has a strict execution time limit, so using a fast language is recommended. (It has been confirmed that AC is achievable with C++, C#, and PyPy3.)

Video

Problem Statement

There is a tree with $N$ vertices. The vertices of this tree are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$.

Edge $i (1 \le i \le N-1)$ connects vertex $u_i$ and vertex $v_i$ and has length $l_i$.

You are given a positive integer $C$ and a vertex sequence $(x_1, x_2, \ldots, x_Q)$ of length $Q$.

Ika is currently at vertex $x_1$ and is about to visit the $Q-1$ vertices $x_2, \ldots, x_Q$ in order.

Ika repeatedly chooses and performs $1$ of the following $3$ actions.

• Choose $1$ edge incident to the current vertex and move to the other $1$ vertex connected by that edge.

  • This action takes time equal to the length $l_i$ of the chosen edge.

• Place $1$ jump beacon on the current vertex.

  • If a beacon is already placed on the tree, it disappears, and only the $1$ beacon at the current position remains.

  • This action takes no time.

• Move to the vertex where the jump beacon is placed.

  • The jump beacon disappears.

  • This action takes time $C$.

Find the minimum time required for Ika to visit the $Q-1$ vertices in order.

Input

$N$ $Q$ $C$
$u_1$ $v_1$ $l_1$
$u_2$ $v_2$ $l_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$ $l_{N-1}$
$x_1$ $x_2$ $\ldots$ $x_Q$

• $2 \le N,Q \le 3{,}000$
• $1 \le C \le 10^9$
• $1 \le u_i, v_i \le N (1 \le i \le N-1)$
• $1 \le l_i \le 10^9 (1 \le i \le N-1)$
• The given graph is a tree.
• $1 \le x_i \le N (1 \le i \le Q)$
• $x_i \ne x_{i+1} (1 \le i \le Q-1)$
• All input values are integers.

Output

Print the minimum time required for Ika to move through the $Q-1$ vertices in order. Print a newline at the end.

Sample

3 5 1
1 2 1000
2 3 10
1 3 2 3 1

1031

6 5 3
1 5 3
6 5 2
4 6 2
3 5 2
5 2 5
1 2 3 4 5

22

2 10 1
1 2 1000000000
2 1 2 1 2 1 2 1 2 1

5000000004