Minimal spanning tree with degree constraint
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&lt;k$, you can now do the following:


For each edge $\{1,v_j\}$ not yet added, determine the most expensive edge on the path from $1$ to $v_j$ in the current tree. Call this edge $e_j$ and compute $d_j = \operatorname{cost}(e_j) - \operatorname{cost}(\{1,v_j\})$, the cost savings of replacing $e_j$ by $\{1,v_j\}$ in the spanning tree.
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) &lt; k$ and the first value $d_j &gt; 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.