Nlogonia’s government is eager to cut down public debt. One of the measures about to take place is the decommission of some highways as most of them incur a high maintenance cost. Each highway connects two different cities and can be traveled in both directions. Using the existing highways it is possible to reach any city from any other city.
Government promises that the impact of the decommission will be minimal in the lives of Nlogonians. In particular they guarantee that after the decommission, for each city the minimum distance needed to travel from that city to the capital of the country will remain the same as it is now, when all the highways can be used.
The Department of Roads of Nlogonia believes that interns are not there just to get coffees or run
errands but should do meaningful work instead and that’s why you are assigned the following task.
Given the length and maintenance cost of each highway, you must decide which highways will be kept
active and which will be decommissioned. As you might guess, the sum of maintenance costs for the
remaining highways must be minimum.