Проще всего - найти произвольный цикл, в нём - ребро наименьшего веса, и вычесть этот вес из всех рёбер. Продолжать, пока циклов не останется. Но результат может быть сильно неоптимальным.
Можно искать цикл, в котором наименьший вес ребра максимален (добавлять рёбра начиная с самого тяжёлого, пока в графе не появится цикл). Тогда результат должен получиться заметно лучше (по сумме весов). Но число рёбер может быть не минимальным.
Кстати, можно ли увеличивать веса дуг (из графа (1,2,w=1), (2,3,w=2), (1,3,w=4) получить (2,3,w=1),(1,3,w=5))? Если да, то после того, как циклы в ориентированном графе кончились, придётся искать циклы в неориентированном графе, и прибавлять ко всем рёбрам наименьший по модулю вес ребра с учётом направления рёбер (вычитать из попутных и прибавлять ко встречным).
Простой
Средний