Поиск кратчайшего пути в графе без каких-либо отрицательных префиксов

Найдите кратчайший путь от источника к месту назначения в ориентированном графе с положительными и отрицательными ребрами, так что ни в одной точке пути сумма ребер, идущих до него, не будет отрицательной. Если такой путь не существует, сообщите и об этом.

Я попытался использовать модифицированный Bellman Ford, но не смог найти правильного решения.

Я хотел бы прояснить несколько моментов:

1. да, могут быть циклы с отрицательным весом.
2. n - количество ребер.
3. Предположим, что существует путь длиной O (n), если проблема имеет решение.
4. + 1 / -1 веса ребер.