Fantastic Network

An undirected weighted graph G = (V,E) is defined as a Fantastic network if it has the following properties:

1. The graph is connected.
2. The degree of any node is at most 6.
3. It may or may not contain cycles, but the length of any cycle (if exists) in this network will be 3. The nodes which are part of at least one cycle are called fine nodes.
4. The degree of any fine node can be at most 3. Here, cycle is defined as a path < v0, v1, . . . , vk > in any graph such that the following statements hold:
5. k ≥ 3. (k is the length of the cycle)
6. v0 = vk.
7. Foreachi(0≤i<K)vi andvi+1 areconnectedbyanedge. 4. v1,...,vk are distinct. An edge dominating set for an undirected graph G = (V, E) is a subset F of E such that every edge not included in F is adjacent to (i.e. shares a vertex with) some edge in F . The weight of an edge dominating set is the sum of the weights of all edges in that set. Given a Fantastic network with positive edge weights, you need to determine the weight of the minimum weight edge dominating set. Input First line of the input contains a positive integer T (T ≤ 100). The first line of each of the T cases contains two integers N (2 ≤ N ≤ 5000) and M (1 ≤ M ≤ 2 ∗ N), representing the number of nodes and edges, respectively, in a Fantastic network. Each of the following M lines contains 3 integers ui, vi, wi, which means there is an edge from ui to vi (1 ≤ ui,vi ≤ n) with weight wi (1 ≤ wi ≤ 10000). Output For each case, print a line of the form ‘Case x: y’, where x is the case number and y is the weight of minimum weight edge dominating set of the given Fantastic network. Sample Input 2 32 121 132 76 122 131

2/2 242 251 362 371 Sample Output Case 1: 1 Case 2: 2