Dijkstra's algorithm is wrong on negative edges. Two other classic algorithms fill the gap: Bellman-Ford (one source, negative weights allowed, detects negative cycles) and Floyd-Warshall (shortest paths between all pairs).
A negative edge and a negative cycle
An edge of negative weight (a gain instead of a cost) is allowed and shortest paths remain well defined. A negative cycle is a cycle whose sum is negative: every lap shortens the path, so a shortest path does not exist (-∞). A good algorithm must detect such a cycle.
Bellman-Ford
A shortest path without cycles has at most V - 1 edges. So it is enough to relax all edges V - 1 times: after pass k the values dist are correct for all paths with at most k edges. One more pass is a test: if some edge still improves, a negative cycle is reachable from the start.
INF = float("inf")