You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

A 村庄现在洪水泛滥！但小 Z 希望能够拯救他们！

村庄一共有 $n$ 个房屋，编号为 $1 \sim n$，房子们被$n-1$ 条边所连，以保证每两个房子都有唯一的路线互相抵达，即村庄中的 $n$ 个房屋形成一棵树。

小 Z 准备开着卡车营救村庄，卡车通过每条路径需要一定时间，有一个基地需要建在某个房屋门口，但是小 Z 不知道应该建在哪个房屋前。

现在一共有 $k$ 个房屋需要被拯救，小 Z 开卡车从基地出发，到达每个房屋，把村民救出。小 Z 要按某个顺序把所有 $k$ 户人家都救出，并留在最后一户人家。每次到达一户人家后他不必返回到基地。

小 Z 现在想知道：对于每一座房屋，当它们设为基地时，完成任务的最小时间分别是多少？

输入格式

从 rescue.in 文件读入数据。

第一行输入两个整数 $n,k$，分别表示房屋数量和需要营救的 $k$ 户人家。

接下来 $n-1$ 行,每行三个整数 $u_i, v_i, w_i (1 \le u_i, v_i \le N)$，表示 $u_i, v_i$ 两个房屋互相抵达需要的时间为 $w_i$。

接下来有 $k$ 行，每行一个整数 $x$，表示编号为 $x$ 的房屋需要被拯救。

输出格式

输出到 rescue.out 文件。

输出 $n$ 行，第 $i$ 行的输出表示把 $i$ 房屋作为基地时,小 Z 到拯救 $k$ 个房屋所需的最少时间。

样例

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

5
3
7
2
2

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

11
15
10
13
16
15
10

样例 3

点击链接 ex_rescue3.in 和 ex_rescue3.out 下载大样例 3 的输入数据和输出数据。

说明/提示

样例 1 解释

如果小 Z 从 $1$ 号房屋开始：他将依次经过 $1-2-4-2-5$；如果从 $2$ 号房屋开始,他将依次经过 $2-5-2-4$。

数据范围

所有测试点，满足 $1 \le w_i \le 10^9$，具体测试点信息如下：