Water Crisis

Water crisis is a severe problem in Dhaka, the capital of Bangladesh. Specially, in summer water crisis is intolerable. WASA (Water and Sewerage Authority) supplies water by container trucks in several places in Dhaka during the summer. But with the increasing demand, WASA is facing difficulty to satisfying the requirements. To devise a solution, WASA is looking for some talented computer scientists who can find the best strategy for WASA. WASA engineers have formulated the water crisis problem in the following way and posed it before the computer scientists. Dhaka city is connected and can be divided into N (N ≤ 20) places where water should be delivered. The road network in Dhaka is quite good and it takes at most 100 minutes from one place to another. Nodes can be numbered from 1 to N and WASA itself is node 1. In each day, the total demand is at most K (K ≤ 200) trucks, but the respective demand (specified in number of trucks) in each place can vary from one another. Like any other government organization, WASA is also lacking resources and it has only 3 working trucks. To simplify the problem, loading-unloading time is assumed to be zero. WASA wants most efficient utilization of its resources and it needs the minimum time by which water is delivered to all the places and all three trucks return to WASA office. Moreover, it may be the case that WASA cannot deliver to all places in a day. If that occurs, you should report ‘Too few trucks’. Input Input will start with an integer T (T ≤ 15) which is the number of test cases. Each input will start with N, followed by (N − 1) integers which are the demand of each place in successive order there is no demand for node 1. The next few lines contain the road network of Dhaka city. Each road is bidirectional and given in the < u v t > format, where u, v are end places and t is the required time (in minutes) to travel through the road. Road network ends with three zeros. Output For each test case, output should start with a line ‘Test Case #: T ’, where T is the test case number. The next line contains the minimum delivery time as specified. If it is more than 20 hrs, you should report Too few trucks. Sample Input 1 4 7 10 3 128 134 141 000 Sample Output Test Case #: 1 66 mins