Recently there is an increasing interest in studying the mixing properties of random walks on random graphs, and there have been multiple recent results proving that various random graph models exhibit cutoff. In this work we consider a model with a lot of structure and only a small amount of randomness. Given a sequence of base graphs $(G_n)$, for each $G_n$ we add edges corresponding to a random perfect matching with weight $\varepsilon_n$, obtaining a weighted random graph $G_n^*$. For $\varepsilon_n\equiv1$ it has been shown (Hermon, Sly, Sousi, 2020) that this added randomness is sufficient to ensure cutoff. We consider what happens for smaller weights, how quickly we can allow $\varepsilon_n$ to approach 0 to still get this effect. For two families of graphs we answer this question exactly, establishing a phase transition in the occurrence of cutoff in $(G_n^*)$ in terms of $(\varepsilon_n)$. We also provide a general condition on $(\varepsilon_n)$ that is sufficient to ensure cutoff. Joint work with Jonathan Hermon, Andela Sarkovic, and Perla Sousi.