Lily cannot forget the night she and Nana ran away together, walking along the railway tracks to explore the truth of the universe, watching the giant fish emerging from the horizon and floating in the night sky. Since then, Lily has never stopped studying the secrets of the universe.

Secrets, there are always one or two. Taking the floating giant fish as a typical example, $n$ major events regarding the universe have occurred in Lily's world. Conspiracies, perfect crimes, dark matter of the universe—the events seem unrelated to each other, but Lily reads books about the universe every day and summarizes $m$ interpretations from the last page of the books, each of which can connect two of these events.

The adults hope that Lily will disclose some of the interpretations she has obtained so that all the events that have occurred can be connected. However, Lily knows that if these interpretations are exposed, about half of the students in her class will start planning to run away—the disclosure of secrets always requires a price from Lily. Assuming the cost of disclosing each interpretation can be quantified, the cost of disclosing the $i$-th interpretation is an integer $w_i$. The total cost Lily needs to pay is the sum of the costs of all the interpretations she discloses, under the condition that the interpretations can connect all the events.

Lily knows that $k$ of these interpretations are key interpretations about the truth of the world, carrying the secrets of 7 billion people. The number of these interpretations disclosed will directly determine the possibility of human continuation. People are arguing, saying that perhaps only these two children can save the world; the justice condensed by 7 billion people has stripped the two of their freedom, urgently wanting to know the answer Lily gives.

You want to know, for all integers $i$ from $0$ to $k$, the minimum total cost Lily needs to pay under the condition that she discloses a portion of the interpretations that can connect all events, and exactly $i$ of them are key interpretations.

"I don't understand," Lily cried like this. She will keep the secrets and wait for the moment to reunite with Nana according to their promise.

Input

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, respectively.

Following this are $m$ lines, each containing three integers $u, v, w$, representing an interpretation that can connect event $u$ and event $v$, but the disclosure of this interpretation requires a cost of $w$.

The first $k$ lines of these $m$ lines represent the key interpretations known to Lily.

Output

Output $k+1$ lines, each containing an integer $ans$. The $i$-th line integer $ans_i$ represents the minimum cost to disclose exactly $i-1$ key interpretations.

The data guarantees that even if no key interpretations are disclosed, the remaining interpretations can connect all events together.

Examples

Input 1

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

Output 1

21
19
20

Constraints

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

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

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

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

By the time this problem was enabled, there were already 8 billion people on the tiny planet.

Figure 1. Lily and Nana running away together