I have a directed graph with $N$ vertices. Every pair of vertices is connected by two edges (one in each direction), and each of these edges has a weight which may be negative.

On various occasions 'edge update' operations occur, where the weight of an edge is modified (although the edge is never deleted, and no new edges or vertices are added). After each of these operations I wish to know the length of the shortest path between one 'root' vertex and every other vertex in the graph. I don't care what the path is, and I already know it must exist. I don't mind how negative weight cycles are handled.

I care about optimizing the running time of the single update operation and the $N$ queries that follow.

The obvious approach would be Bellman-Ford, which would take $O(|V||E|)$ which is $O(n^3)$.

Is there a faster way to do it?