Find the minimum path to every vertex using Bellman-Ford
The algorithm is very similar to Bellman-Ford algorithm except that for each vertex $v$, you maintain $\delta^*(v)$, while in Bellman-Ford algorithm you maintain the length of shortest path from a certain source to $v$.

The correctness of the proof is also similar to that of Bellman-Ford algorithm. More specifically, you prove the following lemma by mathematical induction.


  Lemma. After $i$ repetitions of for loop:
  
  
  If $\mathrm{Distance}(u)$ is not infinity, it is equal to the length of some path from to $u$;
  If there is a path to $u$ with at most $i$ edges, then $\mathrm{Distance}(u)$ is at most the length of the shortest path to $u$ with at most $i$ edges.