Consider a graph with the vertices being the cities and the edges being the roads. By the condition in the problem statement, this graph is a tree.

Let \(D\) be the diameter of this tree. The sought answer is \(2\sum C_i - D\). The diameter of the tree can be found in \(O(N)\) time by the following procedure, so the problem can be solved in \(O(N)\) time.

• From an arbitrary vertex \(v\), find the furthest vertex \(u\).
• From the vertex \(u\), find the furthest vertex \(s\).
• \(u\) and \(v\) are the endpoints of a diameter.

We will not explain why the diameter can be found by the procedure above. We will now prove that the answer to the original problem is \(2\sum C_i - D\).

First, we consider the minimum travel distance when visiting all the vertices at least one and go back to the starting vertex.

For each edge, consider the two connected components obtained by removing the edge; it turns out that every edge has to be passed through at least twice. (This is a lower bound of the answer.)

By performing a DFS (Depth-First Search) from an arbitrary vertex and visiting all the vertices, one can go back to the starting vertex after passing through each edge exactly twice. (The lower bound can be actually achieved.)
Therefore, the answer is \(2\sum C_i\).

We go back to the original problem.

A tour that visits every vertex at least once can be appended by a tour from the ending point to the starting point to form a tour that visits every vertex at least once and goes back to the starting vertex. The minimum value for this is \(2\sum C_i\) as shown above, and the maximum distance of a tour from the ending to the starting point equals the diameter of the tree, so it turns out that the minimum distance of a tour that visits all the vertices at least once is at least \(2\sum C_i-D\). (Lower bound.)

Take an arbitrary diameter with endpoints \(x\) and \(y\). By performing DFS so that “when there are multiple choices of the next vertex to go, choose one that does not go closer to \(y\),” each edge on the shortest path between \(x\) and \(y\) is passed through exactly once. This tour indeed visits every vertex once with the total travel distance \(2\sum C_i-D\). (Lower bound is achievable.)

Hence, the sought minimum value is proved to be \(2\sum C_i-D\).