  The dual graph $\Gamma(h)$ of a regular triangulation $\Sigma(h)$ carries a
natural metric structure. The minimum spanning trees of $\Gamma(h)$ recently
proved to be conclusive for detecting significant data signal in the context of
population genetics. In this paper we prove that the parameter space of such
minimum spanning trees is organized as a polyhedral fan, called the MST-fan of
$\Sigma(h)$, which subdivides the secondary cone of $\Sigma(h)$ into parameter
cones. We partially describe its local face structure and examine the
connection to tropical geometry in virtue of matroids and Bergman fans.
