Consider that a group of criminals was able to rob a bank and got away with a considerable amount of money. However, they were reckless and the security cameras were able to film them. Hence, the police was able to identify everybody in the group. Suppose that the police has a map defined by (L,E), where L denotes the set of locations (with |L| ≤ 106) and E denotes the set of roads connecting those locations (with |L| − 1 ≤ |E| ≤ 106). The map is connected, i.e., for all pairs of locations (u, v) there is always a connecting path in the map. Let f : L×L → N be a function that defines for every road (u,v) ∈ E how many police officers are necessary to make a police road block at road (u,v). Given a set of roads Ec, such that Ec ⊆ E, the value of f(Ec) denotes the total number of police officers necessary to make road blocks in every road (u,v) ∈ Ec. Since the police know the criminals, they were able to identify a set S (with S ⊂ L) of highly suspicious places where the criminals are probably hiding. The purpose of the criminals is to be able to get into a border location in order to get out of the country. The set F defines the set of border locations such that F ⊂ L and S ∩ F = ∅ Therefore, the police needs to make road blocks in a set of roads Ec with Ec ⊆ E in order to ensure that the criminals will not be able to move from the suspected locations to the border without using one of the roads with police road blocks. Your program must determine which is the minimum number of police officers necessary to control a set of roads Ec such that the criminals will not be able to run from the suspected locations to the border. Input The input is as follows: • One line with the number of locations N and the number of roads M in the map. • A list of M lines where in each line there are three integers. The first two are two locations u and v connected in the map and the third is the number f(u,v) of police officers necessary to establish the police road block in that road. • One line with a number S of suspected locations • One line with S integers representing the suspected locations • One line with a number F of border locations • One line with F integers representing the border locations Output The output must be the minimum number of police officers necessary to establish road blocks in a set of roads Ec such that the criminals can not move from the suspected locations to the border without going through a road with a police road block.
2/2 Sample Input 10 13 122 132 244 253 355 364 453 474 576 686 782 7 9 10 8 10 10 2 23 2 9 10 Sample Output 14