05-2 Rendezvous

Our team wants to meet together in one place to do our homework. Our 05-2 team has 22 members. Because of that we are a bit confused on what the best place is to meet one another. So we have decided to meet in the place that has the least total minimum cost. Total minimum cost is defined as the sum of the distance from all source places to destination place. In this problem you are asked to write a program that determines the possible place that has the least total minimum cost. The house of each member is considered as a place here. Input The input consists of at most 105 test cases. The first line of each test case consist two integers N (1 ≤ N ≤ 22) and M (1 ≤ M ≤ (N ∧2−N)/2), specifying the number of members and the number of path. Then it is followed by N lines each consisting of members name, each members name contains at most 10 lower case characters. It is followed by M lines contains three integers i, j (1 ≤ i, j ≤ N ) and k (1 ≤ k ≤ 1000). It means the distance from place i to place j have k cost. If the place i to place j have k cost then from place j to place i have k cost too. The input N = 0 mark as the end of the input. The member number starts from 1. Output For each test cases you should output one line contain like this: “Case #i : XXX” (without quote) where i replaced with the case number and XXX replaced with the member name that have the least total minimum cost. If there are two or more members that have the same least total minimum cost you should output the name of member that appear first. Note: In the first sample input the first name is timotius, second name is harry. This means place 1 is the house of timotius, place 2 is the house of harry, etc. Sample Input 43 timotius harry richard januar 1 2 10 138 146 43 rocky herwin gaston jefry 125

2/2 135 145 00 Sample Output Case #1 : timotius Case #2 : rocky