Description

Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all the farms in the area. Naturally, he needs your help. John has already arranged for a high-speed network line to his farm and wants to share this line with the other farms.

To minimize costs, he wishes to lay the shortest possible fiber optic cable to connect all the farms. You will be given a list of connection costs between pairs of farms, and you must determine the scheme that connects all the farms with the least amount of fiber. The distance between any two farms will not exceed 100,000.

Input Format

• The first line contains the number of farms, N (3 ≤ N ≤ 100).
• The subsequent lines contain an N×N matrix representing the distances between each pair of farms. Theoretically, there are N lines, each consisting of N space-separated numbers. In practice, the lines are limited to 80 characters, so some rows may wrap onto the next line. Naturally, the diagonal elements will be 0, as there is no cost to connect a farm to itself.

Output Format

A single output line containing the minimum total length of fiber required to connect all the farms.

4
0  4  9  21
4  0  8  17
9  8  0  16
21 17 16  0

28