> Bellman-Ford is optimal for positive edge only.

???

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