Rat Tunnel

Arturo bought a large mansion in the Andes of Chile so he can watch the chinchilla, an endangered rodent, up close. The chinchillas live in burrows dug deep under the mansion and chase each other along routes that loop back on themselves. They dig new burrows only once every 30 days.

Arturo asked you to install motion sensing cameras in the burrows so that recording starts by itself whenever a chinchilla passes. Every possible running route must hold at least one camera, and the total cost of the cameras must be as small as possible.

The burrow network is a set of intersections joined by bidirectional lanes. A running route starts at an intersection A, follows two or more lanes, and comes back to A. A single route never travels the same lane twice. The route may start at any intersection.

Cameras go on lanes, not on intersections, and one camera costs exactly the length of the lane it sits on. Choose the lanes that carry cameras so that every possible running route holds at least one camera and the total cost is minimal. Write a program that reports that minimal cost together with the length of the longest lane that carries a camera.

The first line contains the number of test cases $T$. ($0 < T < 1001$)

The first line of each test case contains two integers $S$ and $L$ separated by a blank, the number of intersections and the number of lanes. ($0 < S < 10001$, $0 < L < 100001$) The intersections are labelled $1$ to $S$. Each of the next $L$ lines describes one lane with the labels of the two different intersections it joins and the length of that lane, which is between $1$ and $5000$. More than one lane may join the same two intersections. The whole burrow network is connected.

For each test case, print one line in the form Case #X: D M, where $X$ is the case number starting from $1$, $D$ is the minimal total cost of the cameras, and $M$ is the length of the longest lane that carries a camera. If no camera is needed, print $0$ for both $D$ and $M$.