G - Last Major City Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

AtCoder 国は N 個の都市およびそれらを結ぶ M 本の道路からなり、どの都市間もいくつかの道路を辿ることで行き来可能です。 都市には 1 から N までの番号が、道路には 1 から M までの番号がつけられていて、道路 i は都市 A_i,B_i を双方向に繋いでいます。

交通量が年々増加している AtCoder 国では、いくつかの道路に拡張工事を行うことが予定されています。 現在はまだどの道路も拡張されておらず、道路 i を拡張するのにかかるコストは C_i です。

一度に全ての道路を拡張するのは大変なので、まずは N 個の都市のうち K 個の都市を主要都市に指定し、主要都市間が拡張された道路のみを辿って行き来可能となるような最低限の拡張工事を行うことになりました。 都市 1,2,\dots,K-1 が主要都市に指定されることは既に確定していますが、最後の 1 つの主要都市はまだ決まっていません。

i=K,K+1,\dots,N それぞれについて以下の問いに答えてください。

  • 都市 i が最後の主要都市として指定された場合、どの主要都市間も拡張された道路のみを辿って行き来可能となるようにするための拡張工事のコストの総和の最小値はいくつか。

制約

  • 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
  • どの都市間もいくつかの道路を辿ることで行き来可能である
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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 のときの問いの答えを整数として出力せよ。

入力例 1

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

出力例 1

3
6

上図において、数が書かれた丸はその番号の都市を、数が書かれた線は拡張のためのコストがその数であるような道路を表しています。 また、左右の図はそれぞれ i=3,4 の場合に対応しており、色のついた丸が主要都市を、色のついた太線が最適解において拡張される道路を表しています。

  • i=3 のとき、道路 4,5 を拡張するとコストの総和が 2+1=3 となり、これが最小値です。
  • i=4 のとき、道路 1,4,5 を拡張するとコストの総和が 3+2+1=6 となり、これが最小値です。

入力例 2

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

出力例 2

84
82
56

入力例 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

出力例 3

85
64
94

同じ都市のペアを結ぶ道路が複数存在することもあります。

Score : 600 points

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.