Problem C
Five Rats at Gustav's

Gustav has bought a very fine cheese. On his way home, he was so busy admiring his cheese that he fell into a manhole. He now finds himself in a sewer system with $N$ manholes numbered from $0$ to $N-1$. There are a total of $N-1$ pipes connecting the manholes, and one can move between any pair of manholes by traveling through the pipes. Each pipe takes a certain number of seconds to pass through.

Gustav is located in manhole number $0$, and in the manholes $r_1$, $\dots $, $r_M$, there are rats. Soon, night will fall, and when the night begins, the rats will move toward Gustav. If any rat reaches manhole $0$ before dawn, which occurs $T$ seconds after night begins, they will eat his cheese, and he will be very sad.

To prevent this, he has hacked into the city’s sewer system and can close manholes. If he closes a manhole for $1$ second, no rats can exit that manhole during that second. However, rats can still enter a closed manhole. Gustav wants to keep certain manholes closed during parts of the night so that no rat reaches him before $T$ seconds have passed.

Each manhole has a value $e_i$, representing the energy required to keep the manhole closed for $1$ second. To avoid anyone noticing that he has hacked the sewer system, he wants to use as little energy as possible. What is the minimum total energy he needs to use?

Input

The first line contains the integers $N$, $M$, $T$ ($1 \leq M < N \leq 2 \cdot 10^5$, $1 \leq T \leq 10^8$), the number of manholes, the number of rats, and the number of seconds until dawn.

The next $N-1$ lines contain the integers $a_i$, $b_i$, $t_i$ ($0 \leq a_i,b_i \leq N-1$, $1 \leq t_i \leq 10^8$), indicating that there is a pipe between manhole $a_i$ and manhole $b_i$, and the time required to move between them is $t_i$. It is guaranteed that one can travel between every pair of manholes using the pipes.

After that, a line follows with $N-1$ integers $e_1$, $\dots $, $e_{N-1}$ $(1 \leq e_i \leq 10^5)$, each $e_i$ being the energy required to close manhole number $i$ for one second. Note that Gustav’s manhole is manhole $0$, and $e_0$ is not a given. He can never benefit from closing this manhole since the rats will eat the cheese as soon as they enter it.

Then, a line follows with $M$ integers $r_1$, $\dots $, $r_M$ $(1 \leq r_i \leq N-1)$, where $r_i$ indicates that a rat starts in manhole $r_i$. Initially, there is at most one rat in each manhole.

Output

Print an integer: the minimum amount of energy required to prevent any rat from reaching Gustav before $T$ seconds have passed.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Sample 1

To use the least amount of energy, Gustav should keep manhole number 1 closed during the second, third, and fourth seconds of the night. The rat starting in manhole 2 will travel between manholes 2 and 1 during the first second of the night and remain in manhole 1 for 3 seconds. The rat starting in manhole 3 will travel between manholes 3 and 1 during the first two seconds and will be trapped in manhole 1 for the next two seconds. In the fifth second, both rats will move between manholes 1 and 0. Thus, both arrive at Gustav after exactly 5 seconds and do not get to eat his cheese. The answer is therefore 9.

Explanation of Sample 2

In this testcase, the best strategy is to keep manhole 2 closed during the first second. The rat starting in manhole 2 is trapped there during the first second, then moves between manholes 2 and 1 during the second second and between manholes 1 and 0 during the third second. The rat starting in manhole 3 travels between manholes 3 and 1 for all three seconds. The answer is therefore 3.

4 2 5
0 1 1
1 2 1
1 3 2
3 5 5
2 3

9

4 2 3
0 1 1
1 2 1
1 3 4
5 3 3
2 3

3