Sam, who lives in a node $\backslash ($ s $\backslash )$ of a weighted undirected graph $\backslash ($ G$=($V$,$ E$)\backslash )$ with non$-$negative weights, is invited to a birthday party located at a node $\backslash ($ h $\backslash ).$ Naturally, Sam wants to get from $\backslash ($ s $\backslash )$ to $\backslash ($ h $\backslash )$ as soon as possible, but they are told to buy some beer on the way over. They can get beer at any supermarket, and the supermarkets form a subset of the vertices $\backslash ($ B $\backslash$subseteq V $\backslash ).$ Thus, starting at $\backslash ($ s $\backslash ),$ they must go to some node $\backslash ($ b $\backslash$in B $\backslash )$ of their choice, and then head from $\backslash ($ b $\backslash )$ to $\backslash ($ h $\backslash )$ using the shortest total route possible $($assume they waste no time in the supermarket$).$ Help Sam to reach $\backslash ($ h $\backslash )$ as soon as possible, by solving the following sub$-$problems.

$1.$ Compute the shortest distance from $\backslash ($ s $\backslash )$ to all supermarkets $\backslash ($ b $\backslash$in B $\backslash ).$

$2.$ Compute the shortest distance from every supermarket $\backslash ($ b $\backslash$in B $\backslash )$ to $\backslash ($ h $\backslash ).$ Note that this is the dual of the single$-$source shortest path where we are now asking for the shortest path from every node to a particular destination.

$3.$ Combine part $1$ and $2$ to solve the full problem.