P16618 [GKS 2017 #B] Center

There are $N$ weighted points in a plane. Point $i$ is at ($X_i$, $Y_i$) and has weight $W_i$. In this problem, we need to find a special center of these points. The center is a point ($X$, $Y$) such that the sum of $\max(|X-X_i|, |Y-Y_i|) \times W_i$ is minimum.

The input starts with one line containing exactly one integer $T$, which is the number of test cases. $T$ test cases follow. Each test case begins with one line containing one integer $N$. $N$ lines follow. Each line contains three space-separated real numbers $X_i$, $Y_i$, and $W_i$. $X_i$, $Y_i$ and $W_i$ have exactly 2 digits after the decimal point.

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 sum of $\max(|X-X_i|, |Y-Y_i|) \times W_i$ for center ($X$, $Y$). $y$ will be considered correct if it is within an absolute or relative error of $10^{-6}$ of the correct answer.

**Limits** $1 \le T \le 10$. $-1000.00 \le X_i \le 1000.00$. $-1000.00 \le Y_i \le 1000.00$. **Small dataset (Test set 1 - Visible)** $1 \le N \le 100$; $W_i = 1.0$, for all i. **Large dataset (Test set 2 - Hidden)** $1 \le N \le 10000$; $1.0 \le W_i \le 1000.0$, for all i.