Is the number of shortest paths between every two vertices at most 4*n^3?
Consider the following graph, where we have $3\times 4+1=13$ nodes, $a1, b1, c1, a2, b2, c2, a3, b3, c3, a4, b4, c4, a5$ and $4\times4=16$ edges $a1b1, a1c1, b1a2, c1a2, \cdots, a4b4, a4c4, b4a5, c4a5$ with weights $1,1,1,1,\cdots, 4,4,4,4$ respectively.


Every path from $a1$ to $a5$ is a shortest path between them since all of them have the same weight (length). There are $2^4=16$ of them.

Consider extending this graph to a much larger graph, following the same pattern. For example, suppose we will have $100\times3+1=301$ nodes and $100\times4+1=400$ edges. Now compute how many shortest paths there are between $a1$ and $a301$.



Exercise 1. Construct a graph with the same constraint such that there are more than $4n^3$ paths of the same weight between every two vertices.