Score : $600$ points

问题陈述

AtCoder国家由$N$个城市和$M$条道路连接，可以通过穿越一些道路在任意两个城市之间旅行。城市从$1$到$N$编号，道路从$1$到$M$编号。道路$i$双向连接城市$A_i$和$B_i$。

由于国家交通量的增加，计划扩建一些道路。目前，还没有道路被扩建，扩建道路$i$的成本是$C_i$。

由于一次性扩建所有道路很困难，计划首先指定$K$个$N$个城市作为主要城市，然后进行最少必要的扩建工作，以确保可以通过仅使用扩建的道路在任意两个主要城市之间旅行。已经决定城市$1, 2, \dots, K-1$将是主要城市，但最后一个主要城市尚未决定。

对于每个$i=K, K+1, \dots, N$，回答以下问题：

• 如果指定城市$i$作为最后一个主要城市，确保可以通过仅使用扩建的道路在任意两个主要城市之间旅行所需的扩建工作的最小总成本是多少？

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

The Country of AtCoder consists of $N$ cities and $M$ roads connecting them, and one can travel between any two cities by traversing some roads. The cities are numbered from $1$ to $N$, and the roads are numbered from $1$ to $M$. Road $i$ connects cities $A_i$ and $B_i$ bidirectionally.

Due to increasing traffic in the country, some roads are planned to be expanded. Currently, no roads have been expanded, and the cost to expand road $i$ is $C_i$.

Since it is difficult to expand all roads at once, the plan is to first designate $K$ out of the $N$ cities as major cities and perform the minimum necessary expansion work so that one can travel between any two major cities using only expanded roads. It has already been decided that cities $1, 2, \dots, K-1$ will be major cities, but the last major city has not yet been decided.

For each $i=K, K+1, \dots, N$, answer the following question:

• If city $i$ is designated as the last major city, what is the minimum total cost of the expansion work required to ensure that one can travel between any two major cities using only expanded roads?

Constraints

• $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$
• One can travel between any two cities by traversing some roads.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$ $K$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_M$ $B_M$ $C_M$

Output

Print $N-K+1$ lines. The $l$-th line $(1 \leq l \leq N-K+1)$ should contain the answer to the question for $i=l+K-1$, as an integer.

Sample Input 1

4 5 3
1 4 3
3 4 4
1 2 4
2 3 2
1 3 1

Sample Output 1

3
6

In the above figure, circles with numbers represent cities with those numbers, and lines with numbers represent roads with the cost of expansion being that number. The left and right figures correspond to the cases $i=3$ and $i=4$, respectively. The colored circles represent the major cities, and the colored thick lines represent the roads that are expanded in an optimal solution.

• For $i=3$, expanding roads $4$ and $5$ results in a total cost of $2+1=3$, which is the minimum.
• For $i=4$, expanding roads $1$, $4$, and $5$ results in a total cost of $3+2+1=6$, which is the minimum.

Sample Input 2

4 3 2
2 4 28
1 4 56
1 3 82

Sample Output 2

84
82
56

Sample Input 3

6 12 4
2 6 68
2 5 93
4 6 28
2 4 89
3 6 31
1 3 10
1 2 53
3 5 1
3 5 74
3 4 22
4 5 80
3 4 35

Sample Output 3

85
64
94

There may be multiple roads connecting the same pair of cities.