最后的主要城市

题目描述

AtCoder 国由 $N$ 个城市以及连接它们的 $M$ 条道路组成,任意两个城市之间都可以通过若干条道路互相到达。

城市编号为 $1$ 到 $N$,道路编号为 $1$ 到 $M$。道路 $i$ 双向连接城市 $A_i$ 和城市 $B_i$。

由于国内交通量逐年增加,计划对若干条道路进行扩建工程。

目前还没有任何道路被扩建,扩建道路 $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 \le l \le N-K+1)$ 应输出当 $i=l+K-1$ 时该问题的答案,以整数形式输出。

样例

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

3
6

当 $i=3$ 时,扩建道路 4、5,代价总和为 $2+1=3$,这是最小值。

当 $i=4$ 时,扩建道路 1、4、5,代价总和为 $3+2+1=6$,这是最小值。

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

84
82
56

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

85
64
94

数据范围

• $2 \le N \le 4000$
• $N-1 \le M \le 8000$
• $2 \le K \le \min(N, 10)$
• $1 \le A_i \lt B_i \le N$
• $1 \le C_i \le 10^9$
• 任意两个城市之间都可以通过若干条道路互相到达
• 所有输入值都是整数

提示

可能存在连接同一对城市的多条道路。