Pandaland

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

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 $x_1, y_1, x_2, y_2,$ w, representing there is a road with cost w connecting the cities on $(x_1, y_1)$ and $(x_2, y_2).$

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


$\bullet 1 ≤ T ≤ 50.$
$\bullet 1 ≤ m ≤ 4000.$
$\bullet -10000 ≤ x_i , y_i ≤ 10000.$
$\bullet 1 ≤ w ≤ 10^5.$

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

Hint

jiangzijing2015

Source

2016 CCPC-Final

提交代码