There are a few points on a plane, and some are fixed on the plane, some are not. We want to connect these points by some sticks so that all the points are fixed on the plane. Of course, we want to know the minimum length of the sum of the sticks.

As in the images, the black points are fixed on the plane and red ones are not, which need to be fixed by sticks.

All the points in the left image have been fixed. But the middle one is not, which we need add one stick to fix those four points (the right image shows that stick). Triangle is steady, isn’t it?

As in the images, the black points are fixed on the plane and red ones are not, which need to be fixed by sticks.

All the points in the left image have been fixed. But the middle one is not, which we need add one stick to fix those four points (the right image shows that stick). Triangle is steady, isn’t it?

The input consists of multiply test cases. The first line of each test case contains one integer, n (1 <= n <= 18), which is the number of points. The next n lines, each line consists of three integers, x, y, c (0 <= x, y < 100). (x, y) indicate the coordinate of one point; c = 1 indicates this point is fixed; c = 0 indicates this point is not fixed. You can assume that no two points have the same coordinate.

The last test case is followed by a line containing one zero, which means the end of the input.

The last test case is followed by a line containing one zero, which means the end of the input.

提交代码