Intrepid Climber
Por Cristhian Bonilha, Universidade Tecnológica Federal do Paraná
Brazil
Por Cristhian Bonilha, Universidade Tecnológica Federal do Paraná Brazil
Who would guess? You climbed the highest mountain of your city. You are so excited about it that you need to tell it to all your friends, and you decided to start with those that are trying to be exactly where you are at this precise moment.
The mountain has N landmarks, and one of them is the top of the mountain, where you are now. Each of your friends that is climbing the mountain is in some other landmark, and you want to visit all of them. There are tracks that connect pairs of landmarks in such a way that there exists exactly one route (that is, a sequence of consecutive tracks) that goes down from the top of the mountain to each other landmark. To visit two friends in two different landmarks, you may have to go down some tracks, climb others, and go down others again. Going down the mountain is “easy”, so you do not consume energy when you go down through the tracks. But each time you climb a track, you consume a certain amount of energy. After visiting all your friends, you can just sit and rest.
For example, consider the mountain in the picture below, which has N = 6 landmarks. If your friends are in landmarks 5 and 2, you can visit both if you follow the sequence of landmarks 1 ↓ 2 ↑ 1 ↓ 3 ↓ 5, where a ↓ b means that you go down a track from landmark a to landmark b, and a ↑ b means that you climb a track from landmark a to landmark b. Another possible sequence is 1 ↓ 3 ↓ 5 ↑ 3 ↑ 1 ↓ 2.
Given the tracks between the landmarks, the energy required to climb them, and the landmarks where your friends are, compute the minimum total amount of energy required to visit all your friends from the top of the mountain.
The first line contains two integers N and F (1 ≤ F < N ≤ 105 ), representing respectively the number of landmarks and the number of your friends that are climbing the mountain. Landmarks are identified with distinct integers from 1 to N , being 1 the top of the mountain, where you initially are. Each of the next N − 1 lines describes a different track with three integers A, B and C, indicating that there is a track from A to B that goes down and requires an amount C of energy to be climbed (1 ≤ A ≤ N , 2 ≤ B ≤ N , A != B and 1 ≤ C ≤ 100). The next line contains F different integers L1 , L2 , . . . , LF (2 ≤ Li ≤ N for i = 1, 2, . . . , F ) representing the landmarks where your friends are. You may assume that the tracks between landmarks are such that there exists exactly one route that goes down from the top of the mountain to each other landmark.
Output a line with an integer representing the minimum total amount of energy required to visit all your friends starting from the top of the mountain.
| Ejemplo de Entrada | Ejemplo de Salida |
|
6 2 |
2 |
|
4 2 |
2 |
|
4 2 |
0 |