# 挖地铁

参考时限：2秒；内存限制：512 MiB. 目标平台按正式文件最慢中位数的两倍、向上取整到0.5秒校准，见[评测环境](../../../docs/评测环境与性能.md).

## 背景故事

工务署规划了一张树形地铁网，由 $n$ 个地铁节点和 $n-1$ 段铁路组成，每段铁路隧道都有一个挖掘难度。

现在，小B要去挖地铁。手工挖掘实在太慢，于是他决定用爆破来开通隧道。其中有 $k$ 个节点可以作为爆破起始点，每个起始点都可以重复使用。一次爆破从任意一个起始点出发，到任意一个地铁节点结束，两点之间的铁路隧道便全部挖通。已经挖通的隧道可以再次经过，不会产生负面影响。

小B想知道，挖通全部隧道至少需要多少次爆破，记为 $\mathrm{need}$。但他未必能进行足够多次爆破，所以还想分别知道：进行 $1,2,\ldots,\mathrm{need}$ 次爆破时，挖通隧道的挖掘难度之和最大是多少？每段隧道只计一次。

## 形式化问题描述

给定一棵有 $n$ 个点的无向树，点编号为 $1,\ldots,n$ . 每条边有正整数权值，其中 $k$ 个不同的点被标记。

一次操作选择一个标记点 $s$ 和任意点 $t$ ，覆盖两点间唯一路径上的所有边。允许重复使用同一个标记点、同一条路径，也允许 $s=t$ . 已覆盖的边不会重复计分。

设覆盖全部边所需的最少操作次数为 $\mathrm{need}$ . 对每个 $i=1,\ldots,\mathrm{need}$ ，分别求恰好进行 $i$ 次操作时，已覆盖边的权值之和的最大值。不同的 $i$ 可以选择完全不同的操作方案。

![两条从标记点出发的路径覆盖全部边](assets/example.svg)

图中星号标记点6和7。路径 $6\to3$ 与 $7\to4$ 覆盖全部边，总权值为42.

## 输入格式

第一行两个整数 $n,k$ . 第二行 $k$ 个不同的整数，表示标记点。接下来 $n-1$ 行，每行三个整数 $u,v,w$ ，表示一条权值为 $w$ 的无向边。

## 输出格式

第一行输出 $\mathrm{need}$ . 接下来 $\mathrm{need}$ 行，第 $i$ 行输出恰好 $i$ 次操作的最大覆盖权值。

## 样例 1

### 输入

```text
4 1
1
1 2 2
2 3 2
2 4 1
```

### 输出

```text
2
4
5
```

## 样例 2

### 输入

```text
6 2
1 5
1 2 1
2 3 10
2 4 1
5 4 1
6 4 1
```

### 输出

```text
2
12
14
```

## 样例 3

### 输入

```text
6 2
1 2
1 2 3
2 3 10
2 4 1
5 4 1
6 4 1
```

### 输出

```text
3
13
15
16
```

## 样例 4

### 输入

```text
9 3
4 6 9
1 2 10
2 3 10
3 4 10
3 5 1
2 6 1
3 7 1
7 8 1
7 9 1
```

### 输出

```text
3
30
33
35
```

## 样例 5

### 输入

```text
5 1
1
1 2 2
1 3 3
1 4 4
1 5 5
```

### 输出

```text
4
5
9
12
14
```

## 样例 6

### 输入

```text
7 2
6 7
2 1 5
3 2 5
4 1 9
5 1 4
6 5 10
7 2 9
```

### 输出

```text
2
28
42
```

## 数据范围与保证

$2\le n\le1000$ , $1\le k\le n$ , $1\le w\le100$ . 输入保证是一棵树，标记点互不相同。

本题经授权重新设计：点数上限调整为1000，采用精确算法；覆盖规则、两项输出目标及边权范围保持一致。规格整理与参考实现：Codex（GPT-6）。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |

共10个正式文件，每个10%。[生成说明](tests/README.md)。