What algorithm to apply when a graph have cycles (“circuits”) and some negatives values in order to find the shortest path from $x1$ to all vertices?

What algorithm to apply when a graph have cycles ("circuits") and some negatives values in order to find the shortest path from $x1$ to all vertices? For instance in the following graph? I know I can't use Djikstra...

• Maybe you can add minimal value to all edges? Would it help? Flagging visited vertices to avoid infinite loop? If you cannot use algorithm X, but it is close enough, try resolving issues, and try again. No negative? Remove them... – Evil Jan 2 '16 at 1:40

The Floyd-Warshall algorithm gives costs between all pairs of vertices in reasonable time ($O(n^3)$ for $n$ vertices) as long as there are no negative cost cycles.