P14633 [2018 KAIST RUN Fall] Utilitarianism

在 RUN 国，有 $n$ 个编号为 $1$ 到 $n$ 的城市。一些城市对之间由双向道路连接。恰好总共有 $n-1$ 条道路，并且对于任意两个城市，都存在唯一的路径连接它们。此外，每条道路都被分配了一个整数，称为 **价值**。 今天，为了表彰 RUN 国的 $k$ 位共同创始人，RUN 国的国王 Alex 决定选择 $k$ 条不同的道路，并将每条道路授予一位共同创始人。为避免不必要的冲突，任何城市都不能连接到超过一条被选中的道路。 在这个过程中，RUN 国的国王 Alex 并不关心谁得到哪条道路。相反，Alex 国王只关心这 $k$ 条被选中道路的价值之和。你的任务是选择道路以最大化这个总和。

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 250000$，$1 \leq k \leq n-1$），分别表示 RUN 国的城市数量和要选择的道路数量。接下来的 $n-1$ 行每行包含三个整数 $u, v, c$（$1 \leq u, v \leq n$，$-10^6 \leq c \leq 10^6$），表示城市 $u$ 和城市 $v$ 之间由一条价值为 $c$ 的双向道路直接连接。

如果无法选择 $k$ 条道路满足条件，输出 `Impossible`。否则，输出一个整数，表示被选中的 $k$ 条道路的最大价值总和。

翻译由 DeepSeek V3 完成