P4766 [CERC2014] Outer space invaders

来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。 外星人遵循已知的攻击模式。有 $N$ 个外星人进攻，第 $i$ 个进攻的外星人会在时间 $a_i$ 出现，距离你的距离为 $d_i$，它必须在时间 $b_i$ 及以前被消灭，否则被消灭的会是你。 你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率 $R$，它会瞬间摧毁与你的距离在 $R$ 以内的所有外星人（可以等于），同时它也会消耗 $R$ 单位的燃料电池。 求摧毁所有外星人的最低成本（消耗多少燃料电池），同时保证自己的生命安全。

第一行输入一个数 $T$,表示有 $T$ 组数据。 每组数据的第一行为外星人的数量 $n$（$1\leq n\leq 300$）。 接下来 $n$ 行，每行有三个数 $a_i,b_i,d_i$ ，表示这个外星人在时间 $a_i$ 出现，距离你 $d_i$，在 $b_i$ 前时刻死亡。其中 $1 \le a_i \le b_i \le 10000,1 \le d_i \le 10000$。

共 $T$ 行，每行输出摧毁所有外星人的最低成本。