Problem Description

AtCoder Kingdom consists of $ N $ cities and $ M $ roads connecting them, and it is possible to travel between any two cities by following 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 AtCoder Kingdom, it is planned to expand some of the roads. Currently, no roads are expanded, and the cost to expand road $ i $ is $ C_i $.

Since expanding all roads at once is too costly, it has been decided to designate $ K $ cities as major cities first, and then perform the minimum expansion work necessary so that major cities can travel between each other by following only the expanded roads. It is already determined that cities $1, 2, \dots, K-1$ will be major cities, but the last major city has not been decided yet.

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 needed so that any major city can travel to any other major city by following only the expanded roads?

Input Format

The input is given from the 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 Format

Output $ 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 and Output

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

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

Notes/Hints

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$
• It is possible to travel between any two cities by following some roads.
• All inputs are integers.

Sample Explanation 1

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

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

Sample Explanation 3

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

见题面 Input 部分

见题面 Output 部分