

Orefield DesignTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 235 Accepted Submission(s): 44 Problem Description 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 subplant 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 subplant, 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 subplant 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 subplant on each island, and broaden a shortest length of paths to meet the needs of all the 5 rare minerals. Input 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 ith input mi means the ith village has the mith rare mineral; 0 for the village that does not have rare mineral. (Every village has at most one kind of rare mineral.)  The following n1 lines (from the 3rd to the n+1th line) Each line contains 3 positive integers x, y, d(1<=x, y<=n, 1<=d<=10000), which means the distance between the xth village and the yth 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. Output For each test case, output one line with a positive integer that indicates the shortest length of the paths needed to be broadened. Sample Input
Sample Output
Source  
