“War is God’s way of teaching Americans geography.” Ambrose Bierce (1842 - 1914) The enemy has n cities connected by m roads. We have bombers that can destroy roads. The Bomb, Divide and Conquer strategy dictates that if we separate the enemy’s cities from each other, then the two (or more) pieces will be easier to secure. Bombing a road has a cost (fuel, risk factor, etc.) What is the minimum total cost of bombing enough roads to ensure that there is some pair of cities that have no path between them? A path is a sequence of connected roads. Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with two lines containing n (2 ≤ n ≤ 150) and m (0 ≤ m ≤ n(n − 1)/2). The next m lines contain m triples of integers denoting two different cities (between 1 and n) that are connected by a road and the cost of destroying that road (between 1 and 1000). Output For each test case, output one line containing ‘Case #x:’ followed by the total cost of disconnecting a pair of cities. Sample Input 4 5 4 1 2 100 2 3 299 3 5 400 5 4 99 3 3 1 2 10 2 3 20 1 3 40 4 5 1 2 10 2 3 100 3 4 10 4 1 100 1 3 10 3 1 1 2 1000
2/2 Sample Output Case #1: 99 Case #2: 30 Case #3: 30 Case #4: 0