AT_arc231_a [ARC231A] Two Dimensional Invader

あなたは $ 2 $ 次元平面上に存在する魔法戦士であり，最初は点 $ (0, 0) $ に位置します． これから $ N $ 回のイベントが起こります． $ i $ 回目 ( $ 1 \leq i \leq N $ ) のイベントでは点 $ (X_i, Y_i) $ にモンスターが $ 1 $ 体現れ，あなたはこのモンスターを剣で倒すか魔法で倒すかを選択します． - モンスターを剣で倒すことを選択した場合，あなたは点 $ (X_i, Y_i) $ に移動します．この際，あなたが移動する前に位置していた点と点 $ (X_i, Y_i) $ のユークリッド距離の $ 2 $ 乗のコストがかかります． - モンスターを魔法で倒すことを選択した場合， $ Z_i $ のコストがかかります．この際，移動は行いません． 最終的に必要なコストの総和の最小値を求めて下さい． ユークリッド距離とは 点 $ (a, b) $ と点 $ (c, d) $ のユークリッド距離を $ \sqrt{(a - c)^2 + (b - d)^2} $ と定義します． $ 1 $ つの入力ファイルにつき， $ T $ 個のテストケースを解いてください．

入力は以下の形式で標準入力から与えられる．ここで， $ \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 $

$ T $ 行出力せよ． $ i $ 行目 ( $ 1 \leq i \leq T $ ) には $ \mathrm{case}_i $ に対する答えを出力せよ．

### Sample Explanation 1 - $ 1 $ 番目のテストケースについて， $ 1 $ 回目のイベントと $ 3 $ 回目のイベントではモンスターを剣で倒すことを選択し， $ 2 $ 回目のイベントではモンスターを魔法で倒すことを選択するのが最適です．各イベントでは以下のように進行します． - $ 1 $ 回目のイベントでは，点 $ (0, 0) $ から点 $ (0, 4) $ に移動します．この際，コストが $ 16 $ かかります． - $ 2 $ 回目のイベントでは，コストが $ 11 $ かかります． - $ 3 $ 回目のイベントでは，点 $ (0, 4) $ から点 $ (4, 5) $ に移動します．この際，コストが $ 17 $ かかります． - 最終的に必要なコストの総和は $ 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 $ ) - $ T $ 個のテストケースにおける $ N $ の総和は $ 250\,000 $ 以下 - 入力される値はすべて整数である