Minho's Curiosity

Kangho lives in a country with N cities. The cities are connected by roads, and each road has a travel time. The road network is connected, so it is possible to travel between any two cities.

City A is considered reachable from city B if there is a direct road between them or if one can travel through other cities.

Kangho has made a table of the shortest travel times for every pair of cities. Minho wants to use only this table to find, among all possible original road networks that produce the same shortest-time table, one with the minimum number of roads.

A straightforward road network would put a road between every pair of cities with the travel time shown in the table, but that does not necessarily use the fewest roads. If the travel time between two cities is exactly the same as the time obtained by traveling through other cities, that direct road can be removed without changing any shortest travel time.

Given the shortest travel time between every pair of cities, write a program that prints the sum of all road times when the number of roads is minimized. If no such road network can exist, print -1.

The first line contains the number of cities N (1 <= N <= 20).

Each of the next N lines contains N integers: the travel times between cities. The time from A to B is the same as the time from B to A. The time from a city to itself is 0; every other time is a positive integer not greater than 2500.

Print the sum of all road times when the number of roads is minimized. If it is impossible, print -1.