Connecting the Computers

Special for beginners, ^_^

Problem Description

The school has $n$ computers; to make data transfer convenient, they are now to be connected with data cables. Two computers are "connected" if there is a data cable between them. Because the computers are in different locations, the cost of connecting different pairs is often different.

Of course, connecting every pair of computers directly would be enormously expensive. To save money we use indirect data transfer: one computer can connect to another computer indirectly through several intermediate computers.

It is your job to connect these computers so that every pair of computers is connected (whether directly or indirectly).

Input Format

The first line is an integer $n$ ($2\le n\le100$), the number of computers.

The next $n$ lines each contain $n$ integers. The integer at row $x+1$, column $y$ is the cost of directly connecting computer $x$ and computer $y$.

Output Format

One integer: the minimum connection cost.

Sample Input 1

3
0 1 2
1 0 1
2 1 0

Sample Output 1

2

Constraints

1s, 1024KiB for each test case.