Byteland has N cities (numbered from to ) and N-1 bidirectional roads. It is guaranteed that there is a route from any city to any other city.

Jeanie is a postal worker who must deliver Kletters to various cities in Byteland. She can start and end her delivery route in any city. Given the destination cities for K letters and the definition of each road in Byteland, find and print the minimum distance Jeanie must travel to deliver all K letters.

Note: The letters can be delivered in any order.

The first line contains two space-separated integers, N (the number of cities) and K (the number of letters), respectively. The second line contains K space-separated integers describing the delivery city for each letter. Each line i of the N-1 subsequent lines contains 3 space-separated integers describing a road as ui,vi,di , where di is the distance (length) of the bidirectional road between cities ui and vi.

sample: 5 3 1 3 4 1 2 1 2 3 2 2 4 2 3 5 3

output: 6

path:3-2-1-2-4

approach for this problem

O(V+E) solution intended