Let dist(x) be the current distance from a₁ to x. If adding the edge [a_i, b_i] reduces the value of dist(b_i),  we push the pair {dist(b_i), a_i} to the corresponding vector for b_i. After doing this for i = 1, 2, ..., n,  we can construct the answer by starting with b_n and looking for the pair with first element dist(b_n) in the vector for b_n. The second element of this pair is the second to last node on the path. Letting this node equal p,  we can continue by searching for the pair with first element dist(b_n) - 1 in the vector corresponding to p, and so on.

Code