The TTT Taxi Service in Tehran is
required to deliver some magazines to N locations in Tehran. The locations are
labeled L1 to LN. TTT assigns 3 cars for this service. At time 0, all the 3 cars
and magazines are located at L1. There are plenty of magazines available in L1
and the cars can take as many as they want. Copies of the magazine should be
delivered to all locations, observing the following rules:
The time to go from Li to Lj (or reverse) by any car is a positive integer denoted by D[i , j].
The goal is to organize the delivery schedule for the cars such that the time by which magazines are delivered to all N locations is minimum.
Write a program to compute the minimum delivery time.
The input file contains M instances of this problem (1 <= M <= 10). The first line of the input file is M. The descriptions of the input data follows one after the other. Each instance starts with N in a single line (N <= 30). Each line i of the following N-1 lines contains D[i , j], for all i=1..N-1, and j=i+1..N.
The output contains M lines, each corresponding the solution to one of the input data. In each line, the minimum time it takes to deliver the magazines to all N locations is written.
10 20 3 4
5 10 20