Assuming a directed graph. At the entry to each negative edge collect all the nodes reachable in 1 extra hop from that edge and compute the total cost. All that

Assuming a directed graph. At the entry to each negative edge collect all the nodes reachable in 1 extra hop from that edge and compute the total cost. All that have a positive weight, add as edges from the source of the negative edge. If they still have a negative weight, expand further. Once you're done, drop all the negative edges. This essentially replaces every negative edge with a set of 'shortcuts' that encode all the places the negative edge could have gotten you, such that the shortcuts have positive cost. Use regular Dijkstra on the augmented graph. This obviously has a potentially exponential complexity, though it will work if there isn't too much negativity. It should at least be enough to convince you that preprocessing is possible absent the existence of negative cost loops.