Shortest Network

Problem Background

Special for beginners, ^_^

Problem Description

Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet to the town and connect it to all the farms. Of course, he needs your help. John has already arranged a high-speed network line for his own farm, and he wants to share this line with the other farms. To spend the least money, he wants to lay the shortest fiber to connect all the farms. You will be given a list of the connection costs between farms, and you must find the plan that connects all the farms with the shortest total fiber length. The distance between any two farms will not exceed $100000$.

Input Format

The first line: the number of farms $N$ ($3 \le N \le 100$).

The following lines contain an $N \times N$ matrix, all integers, representing the distance between each pair of farms. Of course, the diagonal will be $0$, because there will be no line from the $i$-th farm to itself.

Output Format

A single output containing the minimum total length of fiber needed to connect every farm.

Sample Input

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

Sample Output

28

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case.