4137. 周游世界

单点时限: 2.0 sec

内存限制: 512 MB

2021 年,蟹老板准备带着老板娘一起周游世界。

世界上一共有 $n$ 个国家,标号从 $1$ 到 $n$。他们由 $n−1$ 条边连接着,经过每条边都有一定的时间花费。任意两个国家之间两两可达。

蟹老板一共决定去 $K$ 个国家。现在他想要知道:如果他从编号为 $i$ 的国家出发,经过所有这 $K$ 个国家的最短时间是多少?(请注意他可以在任意一个国家停下)

输入格式

第一行两个整数 $n,K$,题意如题面所述。

接下来 $n−1$ 行,每行三个整数 $u,v,w$,表示存在一条从 $u$ 到 $v$ 长度为 $w$ 的边。

接下来 $K$ 行,每行一个整数,表示蟹老板想去的某个国家,保证这 $K$ 个国家两两不同。

$1\le K\le n\le 5\times 10^5,1\le w\le 10^6$.

输出格式

输出一共 $n$ 行,其中第 $i$ 行一个整数表示从 $i$ 号点出发所需的最少时间。

样例

Input
3 3
1 2 1
2 3 4
1
2
3
Output
5
6
5
Input
5 2
1 3 1
2 3 2
4 3 3
5 1 4
5
1
Output
4
7
5
8
4

10 人解决,15 人已尝试。

11 份提交通过,共有 91 份提交。

6.6 EMB 奖励。

创建: 3 年,5 月前.

修改: 8 月,4 周前.

最后提交: 2 周,4 天前.

来源: N/A

题目标签