  In a sequence of recent results (PODC 2015 and PODC 2016), the running time
of the fastest algorithm for the \emph{minimum spanning tree (MST)} problem in
the \emph{Congested Clique} model was first improved to $O(\log \log \log n)$
from $O(\log \log n)$ (Hegeman et al., PODC 2015) and then to $O(\log^* n)$
(Ghaffari and Parter, PODC 2016). All of these algorithms use $\Theta(n^2)$
messages independent of the number of edges in the input graph.
  This paper positively answers a question raised in Hegeman et al., and
presents the first "super-fast" MST algorithm with $o(m)$ message complexity
for input graphs with $m$ edges. Specifically, we present an algorithm running
in $O(\log^* n)$ rounds, with message complexity $\tilde{O}(\sqrt{m \cdot n})$
and then build on this algorithm to derive a family of algorithms, containing
for any $\varepsilon$, $0 < \varepsilon \le 1$, an algorithm running in
$O(\log^* n/\varepsilon)$ rounds, using $\tilde{O}(n^{1 +
\varepsilon}/\varepsilon)$ messages. Setting $\varepsilon = \log\log n/\log n$
leads to the first sub-logarithmic round Congested Clique MST algorithm that
uses only $\tilde{O}(n)$ messages.
  Our primary tools in achieving these results are (i) a component-wise bound
on the number of candidates for MST edges, extending the sampling lemma of
Karger, Klein, and Tarjan (Karger, Klein, and Tarjan, JACM 1995) and (ii)
$\Theta(\log n)$-wise-independent linear graph sketches (Cormode and Firmani,
Dist.~Par.~Databases, 2014) for generating MST candidate edges.
