???
CLRS says it takes negative weight edges (just no negative cycles) and does it in O(VE). I have no idea where you're getting this from