#13211Geonosis

After years of planning, the Galactic Empire has built the planetary fortress of Geonosis, a perfect prison for the leaders of the rebelion and a special place reserved for the evil Luke Skywalker. However, as it has been demonstrated with the failures of Death Star I and II, the fortress is not perfect and the evil Rebel Alliance plans to use a weakness detected in the communication towers surrounding Geonosis.

To achieve their evil plans, the Rebel Alliance has stolen a map with the structure of the fortress. Geonosis has a communication complex formed by n towers. Each pair of the complex's tower is connected by power lines that send messages at a w cost of energy.

The rebels want to build the Rogue Two ship to destroy the fortress and rescue its prisoners. To achieve that, they have to destroy all the towers of the fortress. They have discovered that the power necessary to destroy a tower is equal to the sum of the minimum energy needed to send messages between each pair of the fortress towers, either directly or indirectly through other towers. In other words, if we define d(u, v) as the minimum energy to send a message from the tower u to the tower v, the power needed to destroy one tower will be:

Note that once a tower is destroyed, it stops counting for this formula.

3
3
0 35 58
12 0 5
1 2 0
0 1 2
3
0 9982 1413
8327 0 5612
3577 7893 0
1 0 2
4
0 50 10 30
4 0 23 58
2 1 0 5
67 24 25 0
0 3 1 2

96
41118
287