You need some way of remembering the chosen edge each time you do an edge relaxation that changes a distance label.