Subject- Algortihms , Techinques and Theory

please provide an appropirate algortihm and there is no hurry so please help

3. ( 15 points) We say that a digraph G=(V,E) is a "near-DAG" if it is not a DAG and some vertex in V lies on all directed cycles of G. Design and analyze an O(E+V) time algorithm that takes as input a near-DAG G=(V,E) with nonnegative integer edge weights, a vertex u in V that lies on all directed cycles of G, and a distinguished source vertex s in V, and computes the shortest path distance from s to each vertex in V