압수르디스탄의 도로

압수르디스탄 사람들은 작년에야 도로를 놓는 방법을 알아냈다. 그래서 $N$개 도시가 각각 다른 도시로 이어지는 도로를 하나씩 놓았고, 모든 도로는 양방향으로 다닐 수 있다. 도로의 길이는 1 이상 1,000,000 이하의 정수다. 두 도시를 잇는 도로가 둘일 수도 있지만, 한 도시를 자기 자신과 잇는 도로는 없다.

$N$개 도시의 공사는 정확히 1년 만에 끝났고, 공사가 끝난 뒤에는 새 도로만으로 어느 도시에서 어느 도시로든 갈 수 있었다.

관광 안내서에는 새 도로의 지도가 없다. 모든 도시 쌍의 최단 이동 거리를 적은 표만 실려 있다. 같은 표를 만드는 $N$개 도로망이 여러 개일 수 있다. 표가 주어질 때, 표와 맞는 도로망 중 도로 길이의 합이 가장 작은 값을 구하라.

입력은 여러 개의 테스트 케이스로 이루어지고, 파일이 끝나면 입력도 끝난다.

각 테스트 케이스의 첫 줄에 도시의 수인 정수 $N$ ($2 \le N \le 2000$)이 주어진다. 도로의 수도 $N$이다. 이어지는 $N$개 줄에는 각각 정수 $N$개가 주어진다. $i$번째 줄의 $j$번째 정수는 도시 $i$에서 도시 $j$까지의 최단 거리다. $i$에서 $i$까지의 거리는 0이고, $i$에서 $j$까지의 거리는 $j$에서 $i$까지의 거리와 같다. 서로 다른 두 도시 사이의 거리는 모두 양수이고 1,000,000 이하다. 표와 맞는 $N$개 도로망이 적어도 하나 존재한다.

각 테스트 케이스마다 표와 맞는 도로망의 도로 길이 합 중 가장 작은 값을 한 줄에 출력한다.