AT_arc231_a.Two Dimensional Invader

You are a magic warrior on a two-dimensional plane, initially located at point $(0, 0)$.

$N$ events will now occur. In the $i$-th event ($1 \leq i \leq N$), one monster appears at point $(X_i, Y_i)$, and you choose whether to defeat this monster with a sword or with magic.

• If you choose to defeat the monster with a sword, you move to point $(X_i, Y_i)$. This incurs a cost equal to the square of the Euclidean distance between the point where you were located before moving and point $(X_i, Y_i)$.
• If you choose to defeat the monster with magic, a cost of $Z_i$ is incurred. In this case, you do not move.

Find the minimum total cost eventually required.

What is Euclidean distance? The Euclidean distance between point $(a, b)$ and point $(c, d)$ is defined as $\sqrt{(a - c)^2 + (b - d)^2}$.

Solve $T$ test cases per input file.

你是一名位于二维平面上的魔法战士，初始位置为点 $(0, 0)$。

接下来将发生 $N$ 个事件。在第 $i$ 个事件（$1 \leq i \leq N$）中，一只怪物出现在点 $(X_i, Y_i)$，你需要选择用剑或魔法击败该怪物。

• 若选择用剑击败怪物，则你需移动至点 $(X_i, Y_i)$。此次移动产生的代价等于你移动前所在位置与点 $(X_i, Y_i)$ 之间的欧几里得距离的平方。
• 若选择用魔法击败怪物，则产生代价 $Z_i$；此时你无需移动。

求最终所需的最小总代价。

什么是欧几里得距离？点 $(a, b)$ 与点 $(c, d)$ 之间的欧几里得距离定义为 $\sqrt{(a - c)^2 + (b - d)^2}$。

每组输入文件需解决 $T$ 个测试用例。

The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ ($1 \leq i \leq T$) denotes the $i$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_N$ $Y_N$ $Z_N$

输入从标准输入中按以下格式给出。其中，$\mathrm{case}_i$（$1 \leq i \leq T$）表示第 $i$ 个测试用例。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例按以下格式给出：

$N$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_N$ $Y_N$ $Z_N$

Output $T$ lines. The $i$-th line ($1 \leq i \leq T$) should contain the answer for $\mathrm{case}_i$.

输出 $T$ 行。第 $i$ 行（$1 \leq i \leq T$）应包含 $\mathrm{case}_i$ 的答案。

Sample 1 Explanation:

• For the first test case, it is optimal to choose to defeat the monster with a sword in the first and third events, and to choose to defeat the monster with magic in the second event. Each event proceeds as follows.
  • In the first event, you move from point $(0, 0)$ to point $(0, 4)$. This incurs a cost of $16$.
  • In the second event, a cost of $11$ is incurred.
  • In the third event, you move from point $(0, 4)$ to point $(4, 5)$. This incurs a cost of $17$.
• The total cost eventually required is $16 + 11 + 17 = 44$.

Constraints

• $1 \leq T \leq 10$
• $1 \leq N \leq 250\,000$
• $0 \leq X_i < 500$ ($1 \leq i \leq N$)
• $0 \leq Y_i < 500$ ($1 \leq i \leq N$)
• $1 \leq Z_i \leq 10^9$ ($1 \leq i \leq N$)
• The sum of $N$ over the $T$ test cases is at most $250\,000$.
• All input values are integers.

样例 1 解释：

• 对于第一个测试用例，最优策略是在第一场和第三场事件中选择用剑击败怪物，在第二场事件中选择用魔法击败怪物。各事件的具体过程如下：
  • 在第一场事件中，你从点 $(0, 0)$ 移动到点 $(0, 4)$，产生代价 $16$。
  • 在第二场事件中，产生代价 $11$。
  • 在第三场事件中，你从点 $(0, 4)$ 移动到点 $(4, 5)$，产生代价 $17$。
• 最终所需的总代价为 $16 + 11 + 17 = 44$。

约束条件

• $1 \leq T \leq 10$
• $1 \leq N \leq 250\,000$
• $0 \leq X_i < 500$（$1 \leq i \leq N$）
• $0 \leq Y_i < 500$（$1 \leq i \leq N$）
• $1 \leq Z_i \leq 10^9$（$1 \leq i \leq N$）
• 所有 $T$ 个测试用例的 $N$ 值之和不超过 $250\,000$。
• 所有输入值均为整数。