Spanning the Cosmic Secrets

Lily remembers the night when she and Nana escaped, following the railroad tracks in search of the cosmic truth and witnessing a gigantic fish emerging from the horizon. Since that night, Lily has been studying the secrets of the universe. In her world, n major events have occurred, and there are m interpretations linking pairs of these events – each interpretation carries an associated cost w_i. Among these, k interpretations are key revelations carrying the secrets of 7 billion people.

The adults demand that Lily reveal a subset of these interpretations so that all events become connected. However, every revealed interpretation comes at a price. Moreover, depending on how many key interpretations are revealed, the consequences differ greatly. For every integer i from 0 to k, you are to determine the minimum total cost Lily must pay in order to reveal some interpretations that connect all events (i.e. form a spanning tree) and contain exactly i key interpretations.

If no such selection exists for some i, output -1 for that case.

Note: If a formula is needed, use LaTeX format. For example, the cost of a set of interpretations is \(\sum w_i\), and a spanning tree on n events has exactly n-1 interpretations.

inputFormat

The first line contains three integers: n, m, and k, representing the number of events, the number of interpretations (edges), and the number of key interpretations respectively.

Each of the following m lines contains four integers: u v w t. Here, u and v (1-indexed) indicate the events connected by the interpretation, w indicates the cost to reveal this interpretation, and t is either 1 or 0 indicating whether it is a key interpretation (1 for key, 0 for normal).

outputFormat

Output k+1 lines. The i-th line (0-indexed) must contain a single integer – the minimum total cost required to connect all events using interpretations with exactly i key interpretations. If it is impossible to achieve for some i, output -1 for that case.

sample

3 3 1
1 2 1 0
2 3 2 1
1 3 3 0

4
3