SP1794 DRAGON2 - Greedy Hydra II

题目与 [DRAGON](http://www.spoj.com/problems/DRAGON) 描述相同。

第一行给出三个整数 $N$, $M$, $K$，以空格分隔，分别表示果实的数量、分组数量以及位置，整数满足 $1 \le N \le 3000$, $2 \le M \le N$, $1 \le K \le N$。$N$ 个果实依次编号为 $1$ 到 $N$，其中最大的是编号为 $1$ 的果实。接下来的 $N-1$ 行中，每行包含三个整数 $i, j, k$，描述果实 $i$ 和果实 $j$ 之间有一条连接的分支，这条分支的疾病权重为 $k$，其中 $1 \le i, j \le N$ 且 $0 \le k \le 100000$。

输出一个整数，表示分组后的最小疾病权重。如果无法将果实分成 $M$ 组，则输出 `-1`。 **本翻译由 AI 自动生成**