Consider a graph with nonnegative node weight. A vertex subset is called a CDS (connected dominating set) if every other node has at least one neighbor in the subset and the subset induces a connected subgraph. Furthermore, if every other node has at least m neighbors in the subset, then the node subset is called a [Formula: see text]CDS. The minimum-weight [Formula: see text]CDS problem aims at finding a [Formula: see text]CDS with minimum total node weight. In this paper, we present a new polynomial-time approximation algorithm for this problem, which improves previous ratio by a factor of 2/3. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grant U20A2068] and the National Science Foundation [Grant III-1907472]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0306 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0306 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .