Description

There are n computers in a school. To facilitate data transmission, they need to be connected using data cables. Two computers are considered connected if there is a data cable linking them. Due to the different locations of the computers, the cost of connecting any two computers often varies.

Of course, connecting every pair of computers directly with data cables would be prohibitively expensive. To save costs, we adopt an indirect data transmission method, where a computer can be indirectly connected to another through one or more intermediate computers (acting as relays).

Your task is to connect these computers such that any two computers are connected (either directly or indirectly).

Input Format

The first line contains an integer n (2 ≤ n ≤ 100), representing the number of computers.
The subsequent n lines each contain n integers. The integer in the (x+1)-th row and y-th column represents the cost of directly connecting the x-th computer and the y-th computer.

Output Format

A single integer, representing the minimum connection cost.

3
0 1 2
1 0 1
2 1 0

2

Hint

Note: Indicates connecting 1 and 2, 2 and 3, with a cost of 2.