Problem D
05-2 Rendezvous
Input: Standard Input

Output:Standard Output

Our team wants to meet together in one place to doour homework. Our 05-2 team has 22 members. Because of that we are a bit confusedon what the best place is to meet one another. So we have decided to meet inthe place that has the least total minimum cost. Total minimum cost is definedas the sum of the distance from all source places to destination place. In thisproblem you are asked to write a program that determines the possible placethat has the least total minimum cost. The house of each member is consideredas 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 andthe number of path. Then it is followed by N lines each consisting of member’sname, each member’s name contains at most 10 lower case characters. It is followedby M lines contains three integers i, j (1≤ i, j ≤ N) and k (1 ≤ k ≤ 1000). It meansthe distance from place i to place j have k cost.

If the place i to place j have k cost thenfrom 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 replacedwith the case number and XXX replaced with the member name that have the leasttotal minimum cost. If there are two or more members that have the same leasttotal minimum cost you should output the name of member that appear first.

SampleInput                          Output forSample Input