Description
A spanning tree of a graph G = (V, E) is a subset of edges from E that forms a tree connecting all vertices of V. Suppose that G is edge-weighted and all edge weights are positive. Then a minimum product spanning tree of G is defined to be a spanning tree of G that minimizes the product of tree edge weights. Given an edge-weighted graph as shown in Figure 1, for example, the tree shown in Figure 2 is a minimum product spanning tree of this graph. Please write a program to show a minimum product spanning tree of a given edge-weighted graph. In order to make the answer fits in reasonable space, we ask only the natural logarithm of the weight of the spanning tree.
Figure 1: An edge-weighted graph whose weights are positive.
Figure 2: A minimum product spanning tree of the edge-weighted graph as shown in Figure 1.
Input
The input file contains multiple test cases. Each case begins with a line of two integers n (2 ≤ n ≤ 100) and m (1 ≤ m ≤ 4950), where n is the number of vertices and m is the number of edges in the graph. After that, there are m lines each containing three integers u, v and w (1 ≤ u, v ≤ n, u ≠ v, 0 < w ≤ 214) describing an edge of weight w connecting vertices u and v. You may assume that no two vertices are directly connected by more than one edge, and the given graph is connected. There is a blank line between two successive cases, and the input is terminated by end-of-file.
Output
For each case, print “Case i: d” in a line, where i is the test case number starting from 1, and d is the natural logarithm of the product of edge weights in a minimum product spanning tree, rounded to 2 digits after the decimal point. You may assume that the accumulated floating point error would not cause difference to the printed answer. Note that there is a single space character before i and d.
Hint
To calculate the natural logarithm of a number, you may use the “log” function by including
| double | log ( | double x ); |
| float | log ( | float x ); |
| long double | log ( | long double x ); |
This function receives a floating point number x as parameter, and return the natural logarithm of x. Note that in C, only the double version of this function exists with this name.