AtCoder Petrozavodsk Contest 001 D - Forest

解法

まずは、全ての木を連結にするには、それぞれの木について、頂点を少なくとも1つ選んで連結にする必要があるので、それぞれの木から、最もコストが小さい点を1つずつ選んでおきます。
また、コストを最も少なくして全てを連結にするには、 $N$ 頂点の木にする必要があります。ので、辺は $N-1-M$ 本新しく張る必要があり、そのためには $(N-1-M) \times 2$ 個の頂点を使う必要があります。
が、それぞれの頂点は1回ずつしか選択できないので、 $(N-1-M) \times 2 \gt N$ の場合、全ての木を連結にすることはできません。
逆にそれ以外の場合は、最初に選んだ点の個数を $X$ として、 $(N-1-M) \times 2 - X$ 個の頂点を、 $X$ 個に含まれない頂点の中から、コストが小さい順にとっていけば、それらの頂点をうまく組み合わせることで、全ての木を連結にすることができます。