title: Finding the shortest path in a graph without any negative prefixes
body: <blockquote>
    <p>Find the shortest path from source to destination in a directed graph with positive and negative edges, such that at no point in the path the sum of edges coming before it is negative. If no such path exists report that too.</p>
  </blockquote>
  
  <p>I tried to use modified Bellman Ford, but could not find the correct solution.</p>
  
  <hr>
  
  <p>I would like to clarify a few points :</p>
  
  <ol>
  <li>yes there can be negative weight cycles. </li>
  <li>n is the number of edges.  </li>
  <li>Assume that a O(n) length path exists if the problem has a solution.</li>
  <li>+1/-1 edge weights.</li>
  </ol>