Problem: Link I was using Bellman Ford to solve this. To detect a cycle in bellman ford we usually do one more pass on the edges (after n-1) passes and see if anything updated, if yes there is a cycle. But in this problem even if there is a cycle in graph but not a part of path between vertex 1 and n is tolerable. How to detect when to print -1?