#include <bits/stdc++.h>

using namespace std;

const int NMAX = 3300;
const int INF = INT_MAX/3;

int n;
int graph[NMAX][NMAX];
pair<int, int> dist[NMAX];
vector<pair<int, int> > tree[NMAX];
float x_[NMAX], y_[NMAX];
int vis[NMAX];
vector<int> order;

string to_string(int v){
    string ans = "";
    if(v == 0){
        return "0";
    }
    while(v > 0){
        ans += string(1, '0' + v % 10);
        v /= 10;
    }
    reverse(ans.begin(), ans.end());
}

string buildFileName(int num){
    string fileName = "ent";
    if(num < 10){
        fileName += "0";
    }
    fileName += std::to_string(num);
    fileName += ".txt";
    return fileName;
}

int nint(float distance){
    return (int) (distance + 0.5);
}

void readAndBuildGraph(string &fileName){
    int id;
    float readx, ready;
    int read = 0;
    FILE* file = fopen(fileName.c_str(), "r");
    fscanf(file, "%d", &n);
    order.clear();
    for(int i = 0; i <= n; i++){
        tree[i].clear();
        dist[i] = make_pair(INF, -1);
        vis[i] = 0;
    }
    while(read++ < n){
        fscanf(file, "%d %f %f", &id, &readx, &ready);
        x_[id] = readx;
        y_[id] = ready;
    }
    fclose(file);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) if(i != j) {
            float xd = x_[i] - x_[j];
            float yd = y_[i] - y_[j];
            int dij = nint( sqrt(xd * xd + yd * yd) );
            graph[i][j] = dij;
            graph[j][i] = dij;
        }else{
            graph[i][i] = 0;
        }
    }
}

//finding minimum vertex
pair<int, int> findMin(){
    int ans = -1;
    int best = INF;
    int fromNode = INF;
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            if(dist[i].first < best){
                ans = i;
                best = dist[i].first;
                fromNode = dist[i].second;
            }else if(dist[i].first == best){
                if(dist[i].second < fromNode){//in case of tie, getting the lowest index from the tree
                    ans = i;
                    fromNode = dist[i].second;
                }else if(dist[i].second == fromNode){
                    //in case of tie again, we have already got the lowest index
                }
            }
        }
    }
    return make_pair(ans, fromNode);
}

//running prim algorithm
void prim(){
    dist[1] = make_pair(0, 1);//first = distance, second = who I came from
    for(int i = 1; i <= n; i++){
        pair<int, int> best = findMin();
        int newNode = best.first;//new node to join the mst
        int fromNode = best.second;//node that 'newNode' came from
        vis[newNode] = 1;
        if(dist[newNode].second != newNode){//building the tree to run a
            tree[newNode].push_back(make_pair(graph[newNode][treeNode], treeNode));
            tree[treeNode].push_back(make_pair(graph[treeNode][newNode], newNode));
        }
        for(int v = 1; v <= n; v++){
            if(!vis[v] && graph[newNode][v] < dist[v].first){
                dist[v] = make_pair(graph[newNode][v], newNode);
            }
        }
    }
}

void preOrder(int root, int parent){
    //sorting by distance, and if have a tie, by lowest index
    sort(tree[root].begin(), tree[root].end());
    order.push_back(root);
    for(int i = 0; i < tree[root].size(); i++){
        int child = tree[root][i].second;
        if(child != parent){
            preOrder(child, root);
        }
    }
}

int main(){
    srand(time(NULL));
    int m;
    scanf("%d", &m);
    FILE *out = fopen("saida2.txt", "w");
    for(int test = 1; test <= m; test++){
        string fileName = buildFileName(test);
        readAndBuildGraph(fileName);
        prim();
        preOrder(1, 1);
        int ans = 0;
        for(int i = 0; i < order.size(); i++){
            ans += graph[order[i]][order[(i + 1) % order.size()]];
        }
        fprintf(out, "%d\n", (n == 0) ? 0 : ans);
    }
    fclose(out);
    return 0;
}