Problem Description
Mr. Panda lives in Pandaland. There are many cities in Pandaland. Each city can be treated as a point on a 2D plane. Different cities are located in different locations.
There are also M bidirectional roads connecting those cities. There is no intersection between two distinct roads except their endpoints. Besides, each road has a cost w.
One day, Mr. Panda wants to find a simple cycle with minmal cost in the Pandaland. To clarify, a simple cycle is a path which starts and ends on the same city and visits each road at most once.
The cost of a cycle is the sum of the costs of all the roads it contains.
Input
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case begins with an integer M.
Following M lines discribes roads in Pandaland.
Each line has 5 integers x1,y1,x2,y2, w, representing there is a road with cost w connecting the cities on (x1,y1) and (x2,y2).
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the cost Mr. Panda wants to know.
If there is no cycles in the map, y is 0.
limits
∙1≤T≤50.
∙1≤m≤4000.
∙−10000≤xi,yi≤10000.
∙1≤w≤105.
Sample Input
2
5
0 0 0 1 2
0 0 1 0 2
0 1 1 1 2
1 0 1 1 2
1 0 0 1 5
9
1 1 3 1 1
1 1 1 3 2
3 1 3 3 2
1 3 3 3 1
1 1 2 2 2
2 2 3 3 3
3 1 2 2 1
2 2 1 3 2
4 1 5 1 4
Sample Output
Case #1: 8
Case #2: 4
