Let \(D_i\) be the shortest distance from City \(1\) to City \(i\). No matter which roads are chosen, it obviously holds that \(d_i\geq D_i\), so if there is a way to choose roads so that \(d_i=D_i\), then that is the optimal solution. Actually, such a choice always exists.

It is sufficient to retain “the last road in the shortest path from City \(1\) to City \(i\)” for each \(i=2,3,\ldots,N\). We can prove that \(d_i=D_i\) are achieved by induction of the number of roads in the paths.

The answer can be found by recording the last road right before reaching each city during Dijkstra’s algorithm.

Sample code (C++)