Think about a shortest path with negative edges...