SP1461 DRAGON - Greedy Hydra

九头蛇是一种非常贪婪的生物。它出生时有 9 个头，随着成长会不断长出更多的新头，不过也因为老化，旧的头会掉落。 某天，一只拥有 $M$ 个头的九头蛇发现了一棵拥有 $N$ 个果实的树。它欣喜若狂，迫不及待想要吞下所有果实。由于有 $M$ 个头，它必须把这 $N$ 个果实划分为 $M$ 组，确保每组至少有 1 个果实，这样每个头就能吃掉一组果实。 在这些头中，最大的头被称为“老大”。“老大”必须恰好吃掉 $K$ 个果实，其中一定要包含最大的果实。果实编号为 1 到 $N$，编号为 1 的果实是最大的。这 $N$ 个果实通过 $N-1$ 条枝条连接，任何两个果实之间都有路径通过这些枝条连接起来。 如果两颗通过枝条连接的果实被分配到不同的组，对应的两个头就会破坏那条枝条来吃掉这两个果实；否则，这对果实会被同一个头吃掉，而枝条则保持完整。因为吃掉枝条会带来不适，每条枝条都有一个不适度值，九头蛇的总不适度值就是所有被破坏枝条的不适度值之和。 你的任务是帮助九头蛇将总不适度值降到最低。 下图是一个示例：  示例中，$N=8, M=2, K=4$。最大的头吃掉了4个果实（实心点），另一个头吃掉了4个果实（空心点）。用细线标出的枝条被九头蛇破坏并吃掉。

共十个测试用例（顺序给出，你需要分别处理每一个）。每个测试用例的第一行包含三个用空格分隔的整数 $N(1 \le N \le 300)$、$M(2 \le M \le N)$、$K(1 \le K \le N)$。果实的编号为 $1 \dots N$，编号为 1 的果实是最大的。接下来有 $N-1$ 行，每行有三个整数 $i, j, k$，表示果实 $i(1 \le i \le N)$ 和果实 $j(1 \le j \le N)$ 之间有一条枝条，这条枝条的不适度值为 $k(0 \le k \le 100000)$。

输出十行，每行包含一个整数，表示九头蛇的最小总不适度值。如果无法将果实分成 $M$ 组，则输出 `-1`（不带引号）。

- $1 \le N \le 300$ - $2 \le M \le N$ - $1 \le K \le N$ - $0 \le k \le 100000$ **本翻译由 AI 自动生成**