Karger Algorithm with weights

Assume that we are given an undirected, unweighted graph G= (V, E) and some cost function c:E→R>0 assigning a positive cost c(e) to each edge e∈E. The goal is to compute a minimum cut of G of minimum cost (i.e., a minimum cost cut among the cuts consisting of the smallest number of edges). Give an algorithm which with high probability finds such a minimum cost minimum cut in polynomial time. What is the running time of your algorithm? Hint: Karger Algorithm

Approach I: Do Karger n^c times (still polynomial, raises exponent on n of c) and compare resulting min cuts. with c >=1

Approach II: When Karger is taken its edges for Contraction, raise probabilty of High weights. Doesnt affect Runtime

or even a combination of both?