철수는 그의 마을에서 이장으로 선출되었다. 그의 선거공약 중의 하나는 마을 전체를 인터넷으로 연결하겠다는 것이다.

그는 초고속 망을 들여와서 다른 집과 연결 하려고 한다. 비용을 최소화하기 위해 최소한의 선을 이용하여 모든 집을 연결하려 한다.모든 농가는 다른 농가와 연결되어야 한다.

두 농가사이의 거리는 100,000 을 넘지 않는다.

입력

출력

입출력 예

입력

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

출력

28

출처: usaco