Success of semi-supervised clustering algorithms depends on how effectively supervision can be propagated to the unsupervised data. We propose a method for modifying all pairwise image distances when must-link or can't-link pairwise constraints are provided for only a few image pairs. These distances are used for clustering images. First, we formulate a brute-force Quadratic Programming (QP) method that modifies the distances such that the total change in distances is minimized but the final distances obey the triangle inequality. Then we propose a much faster version of the QP that can be applied to large datasets by enforcing only a selected subset of the inequalities. We prove that this still ensures that key qualitative properties of the distances are correctly computed. We run experiments on face, leaf and video image clustering and show that our proposed approach outperforms state-of-the-art methods for constrained clustering.