마법 공방에는 N개의 공명석이 있다. 공명석들은 서로의 진동을 맞추어야 하나의 장치처럼 작동한다. 두 공명석 사이에 동기화 회로를 설치하면, 두 공명석은 즉시 진동을 주고받을 수 있다. 여러 동기화 회로를 거쳐 진동이 전달되어도 전체 장치는 정상적으로 작동한다.

하지만 동기화 회로는 설치한 뒤에도 계속 안정화 비용이 든다. 모든 공명석 쌍 사이에 회로를 설치하면 관리 비용이 너무 커지므로, 공방장은 모든 공명석이 서로 연결되도록 하면서 안정화 비용의 합을 최소로 만들고자 한다. 동기화 회로의 설치 비용은 고려하지 않는다.

공명석은 1번부터 N번까지 번호가 붙어 있다. i번 공명석과 j번 공명석 사이에 동기화 회로를 유지하는 비용은 Cij이며, i = j인 경우에는 항상 0이다.

모든 공명석이 연결되도록 동기화 회로를 선택했을 때 필요한 최소 안정화 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공명석의 수 N이 주어진다. N은 1 이상 1,000 이하이다.

둘째 줄부터 N개의 줄에 걸쳐 각 공명석 사이의 동기화 회로 안정화 비용이 N × N 행렬 Cij로 주어진다. 1 ≤ i, j ≤ N이고, i ≠ j일 때 1 ≤ Cij ≤ 100,000,000이다. 또한 Cij = Cji, Cii = 0을 만족한다.

출력

모든 공명석을 연결했을 때의 최소 안정화 비용을 출력한다.

예제 입력 1

3
0 2 3
2 0 1
3 1 0

예제 출력 1

3

예제 입력 2

5
0 6 8 1 3
6 0 5 7 3
8 5 0 9 4
1 7 9 0 6
3 3 4 6 0

예제 출력 2

11