题目背景

题目描述

若干年后，摸鱼酱当上了摸鱼国的国王。摸鱼国里有 $n$ 座城市，有 $n-1$ 条道路将这些城市连接成了一个树形结构，第 $i$ 条道路连接了城市 $u_i,v_i$，长度为 $w_i$。

有一天，摸鱼国爆发了瘟疫，有 $k$ 座城市都被瘟疫感染了，感染的城市的编号分别为 $c_1,c_2,...,c_k$。作为国王的摸鱼酱决定，选择一座城市在其中修建医院，然后建造一辆救护车。由于某些特殊原因，救护车有一个整数参数 $d$，救护车能够到达某座城市当且仅当这座城市与医院所在城市的最短距离是 $p\times d$ 的形式，其中 $p$ 是一个非负整数，这一趟来回就会花费 $2p$ 个金币。

接下来的 $k$ 天，第 $i$ 天中救护车会前往城市 $c_i$，把那里的病人全部接回医院治疗。因此摸鱼酱希望你帮他选择一座城市建造医院，并且帮他选择救护车的参数 $d$，使得救护车能到达所有被感染的城市，同时让总的花费最小。你只需要告诉他最小的花费即可。

注意，救护车前往某个城市的过程中不需要在中途的城市做停留，只要目的地与起点的距离是 $d$ 的整数倍即可到达。

输入格式

第一行输入两个整数 $n,k$。

第二行输入 $k$ 个整数 $c_1,c_2,...,c_k$。

接下来的 $n-1$ 行，第 $i$ 行输入三个整数 $u_i,v_i,w_i$。

输出格式

输出一行一个整数，表示最小的花费。

输入样例

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

输出样例

8

说明提示

解释：选择在节点 $1$ 修建医院并且设置 $d=6$，被感染的城市到节点 $1$ 的距离分别为 $6,12,6$，因此总花费为 $8$。

【数据范围与提示】

对于 $30\%$ 的数据，$n\leq 1000$。

对于另外 $10\%$ 的数据，$k=n$。

对于令外 $10\%$ 的数据，树是一张菊花图。

对于 $100\%$ 的数据，$1\leq k\leq n\leq 5\times 10^5,1\leq c_i,u_i,v_i\leq n,1\leq w_i\leq 10^7$，$c_i$ 互不相同。

本站补充：原套别：第 14 套 D 题。