Kingdom Roads

In the Kingdom of Graphonia, there are $N$ towns connected by $M$ bidirectional roads, with each pair of towns connected by at most one road. The royal castle is located in the first town (that is, town $1$), and the network is connected, meaning it is possible to travel from the royal castle to any other town using the roads.

To minimize maintenance costs, the king has tasked the royal engineers with closing some roads in the kingdom while ensuring the following requirements are met:

• The network must stay connected.
• The royal castle must have exactly $K$ direct connections to other towns.
• The total maintenance cost of the remaining roads must be minimized.

Task

Help the royal engineers determine the total maintenance cost of the optimized network. If it is impossible to close some of the roads in the required way, write $-1$.

Input data

The first line contains $N$, $M$ and $K$.

The $(i+1)$-th of the following $M$ lines contains three integers, $U_i$, $V_i$ and $C_i$, representing a road between towns $U_i$ and $V_i$ with a maintenance cost $C_i$.

Output data

You need to write a single line with an integer: the unique integer that solves this task.

Constraints and clarifications

• $2 \le N \le 100 \ 000$
• $1 \le M \le 200 \ 000$
• $1 \le K \le d_1$, where $d_1$ is the number of roads from the royal castle to other towns.
• $1 \le U_i, V_i \le N$, $U_i \neq V_i$ for each $i=0\ldots M-1$.
• $0 \le C_i \le 10^9$ for each $i=0\ldots M-1$.
• There is at most one edge between any two nodes and the edges form a connected graph.

Example 1

stdin

5 6 2
1 2 3
1 3 1
1 4 4
2 5 1
3 5 5
4 5 9

stdout

11

Explanation

The first and sixth road of the input must be closed.

Example 2

stdin

4 3 2
1 2 2
1 3 7
1 4 1

stdout

-1

Explanation

There is no way to satisfy the requirements.