Blowing up the roads#1617
There is a direct bidirectional road between each pair of cities in the country. Peter wants to blow up a set of roads so that there exist at least two cities between which travel is impossible.
You are given the cost of blowing up each road. Find the minimal total cost for Peter to achieve this.
Input consists of multiple test cases. The first line of each test case contains the number (n \leq 50) of cities in the country. The next lines describe the roads: the -th character of the -th line is a digit representing the cost of destroying the road from city to city .
For each test case, output on a separate line the minimal total cost for Peter to achieve his goal.
Example 1