Description

FJ has arranged a high-speed network line for his farm, and he wants to share it with other farms. To minimize the cost, he wants to lay the shortest optical fiber to connect all the farms.

You are given a list of connection costs between farms. You must find a plan that connects all farms with the minimum total fiber length. The distance between any two farms will not exceed $10^5$.

Input Format

The first line contains the number of farms $N$ ($3 \leq N \leq 100$).

Next is an $N \times N$ matrix representing the distance between each pair of farms. In theory, it consists of $N$ lines, each with $N$ integers separated by spaces. In practice, due to the $80$-character-per-line limit, some rows may continue directly onto subsequent lines. The diagonal entries are $0$, since there is no line from the $i$-th farm to itself.

Output Format

Output a single integer: the minimum total length of fiber needed to connect all farms.

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

28

Hint

Problem translation from NOCOW. USACO Training Section 3.1.

Translated by ChatGPT 5