피자 배달 최소 시간

한 피자 가게는 주문한 피자를 가능한 한 빠르게 배달하고 싶어 하지만, 고용할 수 있는 배달 기사는 단 한 명뿐이다. 기사는 배달을 시작하기 전에 주문이 $1$개 이상 $10$개 이하로 모일 때까지 기다린다. 기사는 가게에서 출발하여 주문이 들어온 모든 위치에 배달한 뒤 다시 가게로 돌아오는, 가장 짧은 경로를 찾고 싶어 한다. 경로가 더 짧아진다면 도중에 같은 위치나 가게를 여러 번 지나가도 된다. 필요한 최소 총 이동 시간을 구하는 프로그램을 작성하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 배달할 위치의 수를 나타내는 정수 $n$이 주어지며, $1 \le n \le 10$이다. 이어지는 $n + 1$개의 줄에는 각각 $n + 1$개의 정수가 주어지는데, 이는 가게(번호 $0$)와 $n$개의 배달 위치(번호 $1$부터 $n$까지) 사이의 직접 이동 시간을 나타낸다. $i$번째 줄의 $j$번째 값은 다른 곳을 거치지 않고 위치 $i$에서 위치 $j$로 곧바로 이동하는 데 걸리는 시간이다. 일방통행, 속도 제한, 교통 상황 등으로 인해 다른 위치를 거쳐 가는 편이 직접 가는 것보다 빠를 수 있으며, $i$에서 $j$로 가는 직접 이동 시간과 $j$에서 $i$로 가는 직접 이동 시간은 서로 다를 수 있다. $n = 0$인 줄은 입력의 끝을 나타내며, 테스트 케이스가 아니다.

각 테스트 케이스마다, 가게에서 출발하여 $n$개의 모든 위치에 배달하고 다시 가게로 돌아오는 데 필요한 최소 총 이동 시간을 정수 하나로 한 줄에 출력한다.