Doh! Forgot to actually check for negative cycles in relaxEdge.
3 files changed