Complete MST

You are given a complete graph$^{\dagger}$ on $N$ vertices with the edges having weights either $0$ or $1$. Unfortunately you have forgotten which edges had weights of $1$ and which had weights of $0$. But you do remember that there were exactly $M$ edges with weight of $1$. Consider the [Minimum Spanning Tree Problem](https://en.wikipedia.org/wiki/Minimum_spanning_tree) on this complete graph.