410724: GYM104090 M Please Save Pigeland

Some horrible disease called Mysterious Oscar is spreading in Pigeland. The Pigeland has $$$n$$$ cities and is connected by $$$n-1$$$ bi-directional roads. The $$$i$$$-th road is connecting city $$$u_i$$$ and city $$$v_i$$$, with length $$$w_i$$$. It is guaranteed that for every city it is possible to travel to any other city using these roads.

Now, there are $$$k$$$ distinct cities $$$c_1,c_2,\dots, c_k$$$ having the horrible disease. As the leader of the Pigeland, Putata and Budada are going to save the Pigeland. First they will find a city $$$r$$$ to build up a hospital, without considering whether city $$$r$$$ is infected by the disease. Then, they will use the rest of their money to build the only vehicle which could travel in Pigeland, the Pigpigcar. Because they are strapped for cash, they can only build one Pigpigcar, and once a Pigpigcar is built, some parameter $$$d$$$ of the Pigpigcar is set, and could not be changed. The Pigpigcar having parameter $$$d$$$ can only travel from one city to the other, where the distance between the two cities should be a multiple of $$$d$$$. Formally, if you want to travel from city $$$u$$$ to city $$$v$$$, the distance of the shortest path between $$$u, v$$$ should be $$$p\times d$$$, where $$$p$$$ is a non-negative integer, and this would cost $$$p$$$ Pigecoins. Please notice that if you want to travel from city $$$u$$$ to city $$$v$$$, it is not necessary to stop at every city on the path from $$$u$$$ to $$$v$$$, the Pigpigcar can directly go from $$$u$$$ to $$$v$$$, if the minimum distance between $$$u$$$ and $$$v$$$ is a multiple of $$$d$$$.

For the following $$$k$$$ days, Putata and Budada will take the following actions to save the Pigeland. On the $$$i$$$-th day, they will travel to city $$$c_i$$$ from city $$$r$$$ along the shortest path between city $$$r$$$ and city $$$c_i$$$ using the Pigpigcar, cure all the piggies in the city and then travel back to city $$$r$$$ from city $$$c_i$$$.

Putata and Budada want you to choose the proper city $$$r$$$ to build the hospital, and the parameter $$$d$$$ of the Pigpigcar they should build, so that the Pigecoins spent during the travel is minimized. Please help them to find the minimum number of Pigecoins spent.

The first line contains two integers $$$n,k$$$ ($$$1\leq n\leq 5\times 10^5$$$, $$$1\leq k\leq n$$$), denoting the number of cities and the number of cities having disease.

The second line contains $$$k$$$ distinct integers $$$c_1,c_2,\ldots,c_k$$$ ($$$1\leq c_i\leq n$$$), denoting the cities having disease.

For the following $$$n-1$$$ lines, each line contains three integers $$$u,v,w$$$ ($$$1\leq u,v\leq n$$$, $$$u\ne v$$$, $$$1\leq w\leq 10^7$$$), denoting a road connecting city $$$u$$$ and $$$v$$$ with length $$$w$$$.

It is guaranteed that you can go from any city to any other city using these roads.

Output one integer in one line, denoting the minimum number of Pigecoins spent.

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

8

In the sample, you should choose city $$$1$$$ to build hospital and build a Pigpigcar with parameter $$$6$$$, the distance between city $$$1$$$ and city $$$3,4,5$$$ is $$$6,12,6$$$, so the total Pigcoins costed is $$$1\times 2 + 2\times 2 + 1\times 2 = 8$$$.