With the development of science and technology, Cosmic Village has ushered in a new round of network communication equipment renovation. The original base station and all cables were removed. There are $n$ households in Cosmic Village, numbered $1$ to $n$. The new base station numbered $0$. Now the communication company wants to pull some bidirectional cables so that every household can communicate directly or indirectly with the base station. The cost of pulling cables between two positions is known, what is the minimum total cost required to connect all households to the base station?

The first line contains a positive integer $n$. After $n$ lines, the $i+1$-th line contains $i$ numbers, and the $j$-th number $c_{i,j-1}$ represents the cost required to connect the position numbered $i$ to the position numbered $j-1$. $1\le n\le 500$ $1\le c_{i,j-1}\le 10^6$

Print an integer representing the minimum cost to connect all households to the base station.

Clarifications for Sample: COST(1,0)=1 COST(2,0)=1, COST(2,1)=4 COST(3,0)=5, COST(3,1)=1, COST(3,2)=4 So we choose to connect the three cables 0 to 1, 0 to 2 and 1 to 3, the total cost is 1+1+1=3.