  We study the minimum spanning tree problem on the complete graph $K_n$ where
an edge $e$ has a weight $W_e$ and a cost $C_e$, each of which is an
independent copy of the random variable $U^\gamma$ where $\gamma\leq 1$ and $U$
is the uniform $[0,1]$ random variable. There is also a constraint that the
spanning tree $T$ must satisfy $C(T)\leq c_0$. We establish, for a range of
values for $c_0,\gamma$, the asymptotic value of the optimum weight via the
consideration of a dual problem.
