OPTSUB  Optimal Connected Subset
 A point P(x,y) is called an integer point if and only if both x and y are integers.
 W is the set which contains all the integer points on the plane.
 Two integer point P(x,y) and Q(x',y') are called adjacent if and only if xx'+yy'=1.
 S is a set of integer points if and only if S is a limited subset of W.

If S is a set of integer points, R and T belong to S,and there exist a limited integer point sequence Q_{0}(=R),Q_{1},Q_{2},...,Q_{k},Q_{k+1}(=T) which satisfies that
 Q_{i}!=Q_{j} iff i!=j
 Q_{i} and Q_{i+1} are adjacent, for each 0<=i<=k.
 Q_{i} belongs to S, for each 0<=i<=k+1.
 If S is a set of integer points, X and Y are some integer points that belong to S, there exists one and only one path connected X and Y, then S is called an optimal set.
Given an optimal set V, your task is to find an optimal set B, satisfying that B is a subset of V and the sum of the weights of each integer point is maximum.
Input
The very first line of the input contains a single integer T, the number of test cases. T blocks follow.
For each test case, the first line contains a single integer N=V(N<=1000). N lines follow, each contains 3 integers, the Xcoordinate, the Ycoordinate and the weight(the absolute value of the weight<=100) of the ith integer point, separated by single spaces.
Output
T lines,each contains a single integer  the maximum sum of weights.
Example
Input: 1 5 0 0 2 0 1 1 1 0 1 0 1 1 1 0 1 Output: 2
hide comments
Luke Pebody:
20110526 13:55:20
The final part of the definition says "one and only one path" 

:D:
20100529 14:39:09
There can be multiple paths in optimal set. The definition doesn't say anything about one path and the example ((0,0),(0,1),(1,0),(1,1),(2,0)) meets the definion. One point set is an optimal set, because there are no two different points R and T, so the definion is meet by default. 

Luke Pebody:
20100513 10:55:46
Also, is a set of 1 point optimal? 

Luke Pebody:
20100513 10:54:41
Does an optimal set just have 2 points with only one path between them, or do all pairs of points have only one path. For instance, is (0,0),(0,1),(1,0),(1,1),(2,0) an optimal set? 
Added by:  Fudan University Problem Setters 
Date:  20070401 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  Chinese National Olympiad in Informatics 1999,Day 2; translated by Blue Mary 