Задача о непланарном неориентированном графе

[reginaG]

Здравствуйте!

Имеется непланарный неориентированный граф с $n$ вершинами и $m$ ребрами. У каждого ребра вес задан числом от -100 до 100. По условию задачи нужно найти (пометить) все рёбра в этом графе, которые бы удовлетворяли двум условиям:
1) В каждом простом цикле в этом графе должно быть помечено хотя бы одно ребро.
2) Сумма весов всех ребер, соответствующих первому условию, должна быть наименьшей возможной.

Моё решение: Найти все циклы в графе, и в каждом цикле помечать ребро с наименьшим весом.
Но, насколько мне известно, такой подход был бы $NP$, а по условия задания алгоритм должен работать за полиномиальное время (зависим от $n$ и $m$).

Может быть вы могли бы подсказать альтернативный способ решения?

[Null]

1. Все отрицательные ребра помечаем.
2. Пусть веса всех ребер положительны. Надо максимизировать суммарный вес не помеченных ребер.

[slavav]

reginaG, пусть задача решена. Какими свойствами будет обладать совокупность непомеченных рёбер?