There are a lot of cities in Tree Land kingdom and each city is connected to other cities with roads such that there is exists exactly one path to go from one city to any other city. Each road in Tree Land connects exactly two different cities. The king of this kingdom wants to encourage his citizen to have a good sense of natural environmen- tal responsibility. One of his agenda is to promote bicycle, a wheeled human-powered transportation, as the main vehicle for his citizen to travel between places, rather than motor-cycle or auto-mobile which might produce a bad pollution to the environment. In order to determine the progress of his campaign, the king asked the chancellor to monitor the number of bicycles which pass each road in the kingdom. The chancellor executed the king’s order immediately and reported the result to his king, i.e., for each road in the kingdom he reported the number of bicycles passing those roads in one full day. The king was happy, but it didn’t take a long time for him to realize that this report could be misleading. The report only says the number of bicycles passing each road and doesn’t say anything about the total number of bicycles being used in that day. It also doesn’t contain any information on the direction of reported bicycles. For example, consider a city structure shown in the figure (left) below. There are 2 bicycles passing road connecting city A and B, 1 on road connecting B and C, 2 on C - D and 1 on C - E. The total number of bicycles recorded is 2 + 1 + 2 + 1 = 6, but it doesn’t mean the actual number of bicycles used is 6. There could be cases where a bicycle is used to travel between city X and Z passing some other cities, such that this one bicycle is recorded several times, once on each road between X and Z. The figure on the right describes one possibility where there are only 3 bicycles, i.e., one is used to travel between A and B, one is used to travel between A and D passing B and C, and one is used to travel between D and E passing C. Assume that no bicycles are used to pass any road more than once. If a road detects P passing bicycles, then those are P different bicycles. Now your task is to help the king to determine the minimum number of bicycles used on the report. Input The first line of input contains an integer T (T ≤ 10) denoting the number of cases. Each case begins with an integer N (2 ≤ N ≤ 100, 000) denoting the number of cities in the kingdom numbered from 1...N. The next N −1 lines each contains three integers A, B and C (1 ≤ A,B ≤ N; A ̸= B; 0 ≤ C ≤ 100) denoting that there are C bicycles recorded passing road connecting A and B. Note that this N − 1 lines describe the complete city structures in the kingdom. Output For each case, output ‘Case #X: Y ’, where X is case number starts from 1 and Y is the minimum number of bicycles used in the respective case.
2/2 Sample Input 2 5 122 231 342 351 7 121 232 241 253 562 573 Sample Output Case #1: 3 Case #2: 5