Shortest path between all pairs of vertices in cyclic undirected weighted sparse graph
Mikkel Thorup's paper Undirected Single-Source Shortest Paths with Positive
Integer Weights in Linear Time shows an $O(m)$ time algorithm for single-source shortest paths on undirected weighted graphs. That immediately implies an $O(mn)$ time algorithm for all pair shortest paths, which is the optimal $O(n^2)$ in your scenario.