How many shortest distances change when adding an edge to a graph?
Consider the following linear chain with $n+1$ nodes, $n$ edges and viciously chosen weights:


[source]

Clearly, the edges could have been added in order of their weights and there are $n \in \mathcal{O}(|V|)$ of them. Adding the dashed edge (which is legal) creates shorter paths for all pairs $(u_i,b_j)$ with $i,j = 1,\dots,k$. As $k \approx \frac{n}{4}$ and assuming that $n \in \Theta(|V|)$, both first and last row contain $\Theta(|V|)$ many nodes each and the addition causes $\Theta(|V|^2)$ many shortest path changes.

We can now move "outwards" now, i.e. add the next edge with weight $n+2$ between $u_{k-1}$ and $b_{k-1}$ and so on; if we continue this to $(u_1,b_1)$, we cause in total $\Theta(|V|^3)$ shortest path changes.

If this does not convince you, note that you can actually start this "process" with $(c_1,c_2)$ and work outwards from there; this way you add $\approx n$ edges which cause in total $\approx \sum_{i=1}^{n}i^2 \in \Theta(n^3) = \Theta(|V|^3)$ many shortest path changes---this is just impossible to draw to fit on one screen.