AT_abc364_g [ABC364G] Last Major City

AtCoder 国由 $N$ 个城市以及连接这些城市的 $M$ 条道路组成，任意两个城市之间都可以通过若干条道路互相到达。每个城市编号为 $1$ 到 $N$，每条道路编号为 $1$ 到 $M$，第 $i$ 条道路双向连接城市 $A_i$ 和 $B_i$。 由于 AtCoder 国的交通量逐年增加，计划对部分道路进行扩建。目前尚未有任何道路被扩建，扩建第 $i$ 条道路的花费为 $C_i$。 由于一次性扩建所有道路过于困难，首先会从 $N$ 个城市中指定 $K$ 个城市作为**主要城市**，并进行最少的扩建工程，使得所有主要城市之间仅通过已扩建的道路即可互相到达。城市 $1,2,\dots,K-1$ 已经确定为主要城市，最后一个主要城市尚未确定。 请对于 $i=K,K+1,\dots,N$，分别回答以下问题： - 若将城市 $i$ 作为最后一个主要城市，最少需要多少扩建费用，才能使所有主要城市之间仅通过已扩建的道路互相到达？

输入按以下格式从标准输入读入。 > $N$ $M$ $K$ > $A_1$ $B_1$ $C_1$ > $A_2$ $B_2$ $C_2$ > $\vdots$ > $A_M$ $B_M$ $C_M$

输出 $N-K+1$ 行。第 $l$ 行（$1\leq l\leq N-K+1$）输出当 $i=l+K-1$ 时问题的答案，输出一个整数。

### 限制条件 - $2\leq N\leq 4000$ - $N-1\leq M\leq 8000$ - $2\leq K\leq \min(N,\,10)$ - $1\leq A_i < B_i \leq N$ - $1\leq C_i \leq 10^9$ - 任意两个城市之间都可以通过若干条道路互相到达 - 输入均为整数 ### 样例解释 1  如上图，带数字的圆圈表示城市编号，带数字的线表示扩建该道路所需的费用。左右两图分别对应 $i=3,4$ 的情况，带颜色的圆圈为主要城市，带颜色的粗线为最优解中被扩建的道路。 - 当 $i=3$ 时，扩建道路 $4,5$，总费用为 $2+1=3$，这是最小值。 - 当 $i=4$ 时，扩建道路 $1,4,5$，总费用为 $3+2+1=6$，这是最小值。 ### 样例解释 3 可能存在多条道路连接同一对城市的情况。 由 ChatGPT 4.1 翻译