what we generally do in bellman ford:-
every time we relax nodes based on the number of nodes that can be used atmost to relax, what i mean first time we relax all node by a distance of one and than relax all nodes by distance two and keep till we reach n-1 times.
We perform relax operation one all outgoing edges of a node. Now consider a complete graph, every time we relax all the edges going out of a node, and such operation done n-1 time => (n-1) * E+ E*1=o(VE)