76. 景区导游

内存限制:256 MB 时间限制:1.000 S

题目描述

某景区一共有 N 个景点,编号从 1 到 N。景点之间共有 N - 1 条双向的摆渡车线路相连,形成一颗树状结构。

在景点之间往返只能通过这些摆渡车进行,需要花费一定的时间。 小明是这个景区的资深导游,他每天都要按固定顺序带客人游览其中 K 个景点,A1, A2, ..., Ak。今天由于时间原因,小明决定跳过其中一个景点,只带游客按顺序游览其中 K - 1 个景点。

具体来说,如果小明选择跳过Ai,那么他会按顺序带领游客游览A1, A2, ..., Ai-1, Ai+1, ..., Ak(1 <= i <= k)。 请你对任意一个 Ai,计算如果跳过这个景点,小明需要花费多少时间在景点之间的摆渡车上。

输入

第一行包含两个整数 N 和 K。

以下 N - 1 行,每行包含 3 个整数,u、v 和 t,代表景点 u 和景点 v 之间有摆渡车线路,花费 t 个时间单位。

最后一行包含 K 个整数 A1, A2, ..., Ak,代表原定游览线路。

输出

输入 K 个整数,其中第 i 个代表跳过 Ai 之后,花费在摆渡车上的时间。

样例输入 复制

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

样例输出 复制

10 7 13 14