Alien Invaders

Aliens have invaded Earth. If you do not defend yourself, you die. Or you get assimilated. You might even get eaten. Nobody is quite sure which.

The aliens attack on a fixed schedule. There are $n$ aliens, and alien $i$ appears at time $a_i$ at distance $d_i$ and attacks you at time $b_i$. You therefore have to destroy alien $i$ at some time between $a_i$ and $b_i$, inclusive.

Your weapon is a photon bomb whose blast power you can set to any value. If you set the power to $R$ and detonate the bomb, every alien that is on the field at that moment and stands at distance at most $R$ dies instantly, and the bomb burns $R$ units of fuel. You may detonate a bomb at any time and as many times as you want.

Find the smallest amount of fuel that destroys every alien without letting any of them attack you.

The first line has the number of test cases $T$.

Each test case starts with a line holding the number of aliens $n$ $(1 \le n \le 300)$. The next $n$ lines hold $a_i$, $b_i$, $d_i$ $(1 \le a_i < b_i \le 10000,\ 1 \le d_i \le 10000)$ for alien $i$, separated by spaces.

For each test case, print the smallest amount of fuel that destroys every alien, one answer per line. The answer is always an integer.