Battle over cities(Hard Version)

 Battle Over Cities - Hard Version   (20分) It is vitally important to have all the cities connected by highways in a war. If a city is conquered by the enemy, all the highways from/toward that city will be closed. To keep the rest of the cities connected, we must repair some highways with the minimum cost. On the other hand, if losing a city will cost us too much to rebuild the connection, we must pay more attention to that city. Given the map of cities which have all the destroyed and remaining highways marked, you are supposed to point out the city to which we must pay the most attention. Input Specification: Each input f