 Solution

Let $N=|V|$ and replace every edge weight by $w^{\prime }(e)=Nw(e)+1$. Call the supplied shortest-path routine once using these new weights, and return its path in the original graph. For every path $P$,where $|P|$ is its number of edges. Positive original weights imply positive transformed weights, so a shortest route can be taken to be simple and has at most $N-1$ edges. Distinct integral original weights of paths differ by at least one. Thus if $w(P)<w(Q)$ for simple paths, thenFor equal original weights, the transformed comparison is exactly the comparison of hop counts. Therefore every transformed shortest path minimises original weight first and number of edges second, proving the integer-weight shortest-path tie-breaking lemma. The transformation costs $O(N+|E|)$ time, followed by one subroutine call. Weights gain only $O(\log N)$ bits; exact arithmetic should be used if multiplying machine-sized weights might overflow. If $t$ is unreachable, it remains unreachable.