P3905 Road Reconstruction

Once, in a kingdom, there were $m$ roads connecting $n$ cities, and between any two cities there was at most one direct road. After a severe war, $d$ roads were destroyed. The king wants to repair the country's road system. Now, traffic between two important cities $A$ and $B$ is interrupted, and the king hopes to restore the connection between these two cities as soon as possible. Your task is to repair some roads to restore the connection between $A$ and $B$, while minimizing the total length of the repaired roads.

The first line contains an integer $n\ (2

Output a single integer, representing the minimal total length of roads that must be repaired to restore traffic between $A$ and $B$.

Translated by ChatGPT 5