AT_arc231_a [ARC231A] Two Dimensional Invader

你是一个二维平面上的魔法战士，初始位于点 $ (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 $ 个测试用例。

输入从标准输入按以下格式给出，其中 $ \mathrm{case}_i $（$ 1 \leq i \leq T $）表示第 $ i $ 个测试用例。 > $\begin{aligned} &T \\ &\mathrm{case}_1 \\ &\mathrm{case}_2 \\ &\vdots \\ &\mathrm{case}_T \end{aligned}$ 每个测试用例按以下格式给出： > $\begin{aligned} &N \\ &X_1 Y_1 Z_1 \\ &X_2 Y_2 Z_2 \\ &\vdots \\ &X_N Y_N Z_N \end{aligned}$

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

### 样例 #1 解释 - 对于第一个测试用例，最优方案是：第 1 个和第 3 个事件选择用剑击败怪物，第 2 个事件选择用魔法击败怪物。各事件如下： - 第 1 个事件，从点 $ (0, 0) $ 移动到点 $ (0, 4) $。代价为 $ 16 $。 - 第 2 个事件，产生代价 $ 11 $。 - 第 3 个事件，从点 $ (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 $。 - 所有输入值均为整数。