Absurdistan Roads

The people of Absurdistan worked out how to build roads only last year. Every one of the $N$ cities then built exactly one road from itself to another city, and every road can be travelled in both directions. Each road has an integer length between 1 and 1,000,000. Two cities can end up joined by two roads, but no road joins a city to itself.

The work took all $N$ cities precisely one year, and once it was finished, every city could reach every other city over the new roads.

Your tourist guide has no map of the new roads. It only prints a table with the shortest travelling distance between every pair of cities. Several different networks of $N$ roads can produce the same table. Given the table, find the smallest possible total length of the $N$ roads.

The input holds several test cases and ends at the end of the file.

Each test case starts with a line holding an integer $N$ ($2 \le N \le 2000$), the number of cities, which is also the number of roads. The next $N$ lines hold $N$ integers each. The $j$-th integer on the $i$-th line is the shortest distance from city $i$ to city $j$. The distance from $i$ to $i$ is 0, the distance from $i$ to $j$ equals the distance from $j$ to $i$, and every distance between two distinct cities is positive and at most 1,000,000. At least one network of $N$ roads matches the table.

For each test case, print one line with the smallest possible total length of the $N$ roads.