Pizza Delivery Minimum Time

A pizzeria wants to deliver its pizzas as fast as possible, but it can afford only one driver. Before setting out, the driver waits until between $1$ and $10$ orders have been placed. He wants the shortest possible route that starts at the pizzeria, delivers to every ordered location, and returns to the pizzeria. He is allowed to pass through any location, or the pizzeria itself, more than once along the way if that makes the route shorter. Write a program that computes the minimum total travel time.

The input contains multiple test cases. Each test case begins with a line holding a single integer $n$, the number of locations to deliver to, with $1 \le n \le 10$. The next $n + 1$ lines each contain $n + 1$ integers describing the direct travel times among the pizzeria (numbered $0$) and the $n$ delivery locations (numbered $1$ to $n$). The $j$-th value on the $i$-th of these lines is the time to travel directly from location $i$ to location $j$ without stopping anywhere else. Because of one-way streets, speed limits, and traffic, a detour through other locations may be faster than the listed direct time, and the direct time from $i$ to $j$ need not equal the direct time from $j$ to $i$. A line containing $n = 0$ marks the end of the input and is not a test case.

For each test case, print a single line containing one integer: the minimum total time needed to start at the pizzeria, deliver to all $n$ locations, and return to the pizzeria.