The Aizu Wakamatsu city office decided to lay a hot water pipeline covering the whole area of the city to heat houses. The pipeline starts from some hot springs and connects every district in the city. The pipeline can fork at a hot spring or a district, but no cycle is allowed. The city office wants to minimize the length of pipeline in order to build it at the least possible expense.
Write a program to compute the minimal length of the pipeline. The program reads an input that consists of the following three parts:
For the sake of simplicity, you can assume the following:
The input has several test cases. The input terminate with a line which has two 0.
Output the minimum length of pipeline for each test case.
3 5 12 8 25 19 23 9 13 16 0 17 20 14 16 10 22 17 27 18 16 9 7 0 19 5 21 0 0
The first line correspondings to the first part: there are three hot springs and five districts. The following three lines are the second part: the distances between a hot spring and a district. For instance, the distance between the first hot spring and the third district is 25. The last four lines are the third part: the distances between two districts. For instance, the distance between the second and the third districts is 9. The second hot spring and the fourth district are not connectable The second and the fifth districts are not connectable, either.