Background

Some unnecessary images are omitted.

Problem Description

Lily cannot forget the night in her childhood when she ran away together with Nana before they parted. In order to explore the truth of the universe, they walked along the railway tracks and saw huge fish surging from the horizon, floating in the night sky. From then on, Lily never stopped studying the secrets of the universe.

Secrets always exist, one or two of them. With the floating fish as a typical example, there were $n$ major events about the universe in Lily’s world. Intrigue, perfect crimes, the universe’s dark matter—these events seem unrelated to each other. But Lily reads books about the universe every day, and from the last page of the books she summarizes $m$ pieces of interpretation. Each piece of interpretation can connect two of the events.

Adults hope Lily will reveal some of the interpretations that have already been obtained, so that all events can be linked together. But Lily knows that if these interpretations are exposed, probably about half the classmates will start planning to run away. Revealing secrets always costs Lily something. Suppose the cost to reveal each interpretation can be quantified: the cost to reveal the $i$-th interpretation is an integer $w_i$. The total cost Lily needs to pay is the sum of the costs of all interpretations she reveals, under the condition that the revealed interpretations can connect all events together.

Lily also knows that among them there are $k$ key interpretations about the truth of the world, carrying the secret of $7$ billion people. How many of these interpretations are revealed will directly determine the possibility of humanity continuing. People argue and say that perhaps only these two children can save the world; the justice of $7$ billion people deprives the freedom of $2$ people, and they eagerly want to know Lily’s answer.

You want to know, for every integer $i$ from $0$ to $k$, under the condition that Lily reveals some interpretations that can connect all events, and among them there are exactly $i$ key interpretations, what is the minimum total cost Lily has to pay.

“I don’t understand,” Lily cried like this. She will hold on to the secret, and wait according to the promise for the moment she meets Nana again.

Input Format

The first line contains three integers $n, m, k$, representing the number of events, the total number of interpretations, and the number of key interpretations.

Then follow $m$ lines, each containing three integers $u, v, w$, representing an interpretation that can connect event $u$ and event $v$, but revealing this interpretation costs $w$.

Among these $m$ lines, the first $k$ lines represent the key interpretations known by Lily.

Output Format

Output $k + 1$ lines, each containing one integer $ans$.

In particular, the integer $ans_i$ on the $i$-th line indicates the minimum total cost when revealing exactly $i - 1$ key interpretations.

The testdata guarantees that even if none of the key interpretations are revealed, the remaining interpretations can still connect all events together.

5 8 2
3 4 6
2 1 6
1 4 8
1 2 10
2 3 4
3 4 5
4 5 4
2 4 6

21
19
20

Hint

Constraints

$1 \le u, v \le n, 1 \le w \le 10^9$.

For $30\%$ of the testdata, $1 \le n \le 100$, $1 \le m \le 400$, $1 \le k \le 5$.

For another $30\%$ of the testdata, $1 \le n \le 10000$, $1 \le m \le 1000000$, $1 \le k \le 20$.

For the remaining $40\%$ of the testdata, $1 \le n \le 10000$, $1 \le m \le 1000000$, $1 \le k \le 50$.

When the contest problem was activated, there were already $8$ billion people on the small planet.

Translated by ChatGPT 5