AT_abc364_g [ABC364G] Last Major City

[problemUrl]: https://atcoder.jp/contests/abc364/tasks/abc364_g 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 $ が最後の主要都市として指定された場合、どの主要都市間も拡張された道路のみを辿って行き来可能となるようにするための拡張工事のコストの総和の最小値はいくつか。

入力は以下の形式で標準入力から与えられる。 > $ 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\