Minimal spanning tree with degree constraint

I have to solve this problem: We have weighted $n$-node undirected graph $G = (V,E)$ and a positive integer $k$. We can reach all vertices from vertex 1 (the root). We need to find the weight of minimal spanning tree in which the degree of vertex 1 is at most $k$ (we don't care about other vertices' degrees). We can assume that such a tree exists.

Can someone give an idea how to approach the solution?

What I've already tried:

1) I know how to find essential edges from vertex 1. We can use dfs and start from a random edge of vertex 1. When we return to vertex 1 we can check if this edge (another vertex 1 edge) has lower weight than the previous one. If yes, than the previous one is not essential.

2) After that I wanted to use Kruskal's algorithm (adding in the beginning of the algorithm all essential edges). But the problem is that sometimes we should not take an edge with minimal weight to construct the required tree.

For example: 9-node undirected graph, $k = 3$

(vertex1 vertex2 weight)
1 2 1
2 3 5
3 4 6
4 5 7
5 1 1
1 6 1
6 7 8
7 8 9
8 9 10
9 1 2

So essentials will be (1,2) and (1, 6) (or (1, 5) and (1,6)). Kruskal will take (1,5) (or (1,2)) anyway. And the weight will be 41, but the correct answer is 39.
So I don't know how to use Kruskal's algorithm here.

(The same example visualized, vertex 1 = vertex A)

I thought that we may construct a minimal spanning tree without constraints and after that try to transform it to the required one, but I don't know how to do this (how to transform without brute force).

As D.W. suggested, you can start as follows:

• Temporarily delete vertex $1$.

• For each of the resulting connected components $C_1, \dotsc, C_m$ find a MST, using e.g. Kruskal's or Prim's algorithm.

• Re-add vertex $1$ and for each $C_i$ add the cheapest edge between $1$ and $C_i$.

• If $m=k$, you are done.

If $m

• Create a priority queue of the tuples $(v_j, e_j, d_j)$, ordered by decreasing value of $d_j$.

• As long as $\operatorname{deg}(1) 0$, consider the first tuple from the proority queue:

• If $e_j$ has already been removed, find the edge $e_j$ and the value $d_j$ corresponding to the current tree. Update the tuple and its position in the priority queue.

• Otherwise replace $e_j$ by $\{1,v_j\}$ in the spanning tree and remove the tuple from the queue.

Finding $e_j$ can be done in ${\cal O}(n)$, using e.g. a modified DFS. This makes the second phase ${\cal O}(n^2)$. Since Prim's algorithm is ${\cal O}(n^2)$ as well, this is also the running time for the complete algorithm.

StackExchange Computer Science Q#22775, answer score: 3