Orefield Design

The XYZ Corporation has found 5 rare minerals, which are located on different regions of several islands along the East Coast of the Pacific. The company believes that it would be a best opportunity to gain profits. However, due to the financial crisis, the company does not have enough manpower or money spending in building orefields on all the islands. Therefore, the Committee has chosen some islands that have relatively higher ore storages, and sent one investigator to each of these islands to make a survey of the ore distribution on the island. The survey results show that each island has many villages which are connected with paths. Because of the time consuming, the investigator does not record all the paths on his map. Instead, according to his map, there is one and only one way to go from one village to another(map is drawn like a tree).

The company plans to establish a sub-plant on one of the villages in each of the chosen islands. All the 5 rare minerals dug from different locations of that island will be sent to this sub-plant, and after being made into a kind of compound metal. To minimize the cost on building transportation road, the company decides to broaden the original paths rather than constructing new roads. Moreover, the company determines to build the orefields in the villages to make sure they can hire enough workers. (If the sub-plant is located in one village, the orefields can also be built in that village.)

Since the ore storages in these islands are very high, each kind of rare minerals only needs one orefield. Now given the maps of the chosen islands, you need to find the most appropriate village as the sub-plant on each island, and broaden a shortest length of paths to meet the needs of all the 5 rare minerals.

Input contains multiple test cases.

For each test case:

- The first line contains a positive integer n (5<=n<=1000), which means the number of villages on the island.

- The second line contains n positive integer m1, m2, ... mn(0<=mi<=5), which indicates which kind of rare minerals that village has. eg. The i-th input mi means the i-th village has the mi-th rare mineral; 0 for the village that does not have rare mineral. (Every village has at most one kind of rare mineral.)

- The following n-1 lines (from the 3rd to the n+1-th line)

Each line contains 3 positive integers x, y, d(1<=x, y<=n, 1<=d<=10000), which means the distance between the x-th village and the y-th village is a path with the length d.

Value of n = 0 terminate input.

Note: you can assume that all the given island has all the 5 minerals.

For each test case, output one line with a positive integer that indicates the shortest length of the paths needed to be broadened.

6
1 2 3 4 5 5
1 2 100
2 3 82
3 4 73
4 5 120
4 6 108
6
1 1 2 3 4 5
1 2 56
1 3 100
1 4 100
2 5 100
3 6 100
0

363
456

2009 Multi-University Training Contest 9 - Host by HIT