Statement

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: (1) The network must stay connected. (2) The royal castle must have exactly K direct connections to other towns. (3) The total maintenance cost of the remaining roads must be minimized. 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.