  We consider the following question. We have a dense regular graph $G$ with
degree $\alpha n$, where $\alpha>0$ is a constant. We add $m=o(n^2)$ random
edges. The edges of the augmented graph $G(m)$ are given independent edge
weights $X(e)$, $e\in E(G(m))$. We estimate the minimum weight of some
specified combinatorial structures. We show that in certain cases, we can
obtain the same estimate as is known for the complete graph, but scaled by a
factor $\alpha^{-1}$. We consider spanning trees, shortest paths, perfect
matchings in (pseudo-random) bipartite graphs.
