在一个被洪水淹没的村庄里，一个秘密的超级人道主义营地正在建立。村庄由 $N$ 栋房屋组成，编号为 $1$ 到 $N$。这些房屋之间由 $N-1$ 条道路连接，使得任意两栋房屋之间都有唯一的一条路径。对于每条道路，我们知道卡车通过它所需的时间。营地应该建在某栋房屋的花园里，但营地主管还没有决定具体建在哪个房屋。

Mirko 被任命为司机。他的工作是开着他的超级卡车，将志愿者队伍从营地送到各个队伍工作的房屋。他的卡车非常“超级”，因为所有队伍都可以同时乘车！总共有 $K$ 支队伍，每支队伍都将前往不同的房屋。

所有 $K$ 支队伍最初都登上 Mirko 的卡车，然后他按照自己决定的顺序将他们送到各自的房屋。在送完所有队伍后，Mirko 会留下来帮助最后一支队伍（他不需要返回营地）。

为了让营地主管决定将营地建在哪里，他想知道，对于每栋房屋，如果将该房屋作为总部，Mirko 送完所有队伍所需的最短时间。写一个程序来计算出 Mirko 的老板想要知道的这些数值！

输入格式

第一行包含两个整数 $N$ ($1 \le N \le 500\,000$) 和 $K$ ($1 \le K \le N$)。

接下来的 $N-1$ 行，每行包含三个整数 $A_i, B_i, C_i$ ($1 \le A_i, B_i \le N$, $1 \le C_i \le 1\,000\,000$)，表示连接房屋 $A_i$ 和 $B_i$ 的双向道路，通过该道路需要的时间为 $C_i$。

接下来的 $K$ 行，每行包含一个整数，分别表示第 $i$ 支队伍要去的房屋编号。

输出格式

输出 $N$ 行。第 $i$ 行输出如果营地总部设在第 $i$ 栋房屋，Mirko 送完所有队伍所需的最短时间。

子任务

对于 $50\%$ 的测试数据，满足 $N \le 2\,000$。

样例

输入样例 1

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

输出样例 1

5
3
7
2
2

输入样例 2

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

输出样例 2

11
15
10
13
16
15
10

说明

样例 1 说明

如果 Mirko 从房屋 1 出发，他可以依次沿着 1-2-4-2-5 的路线放下志愿者。如果他从房屋 2 出发，可能的路线为 2-5-4。