Minimum Total Energy to Connect Towers

You are given one or more datasets representing tower configurations. Each tower is described by its coordinates and an energy parameter (which is not used in the computation). Your task is to connect all towers with a network such that the total energy required is minimized.

The energy required to connect two towers is equal to the Euclidean distance between them. In other words, if two towers have coordinates \((x_1, y_1)\) and \((x_2, y_2)\), then the energy needed to connect them is \[ \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} \]

Compute the minimum total energy required to form a spanning network that connects all towers. Round the final result to the nearest integer.

This problem can be solved by using Prim's algorithm to find a Minimum Spanning Tree (MST) of the towers.

inputFormat

The first line contains an integer \(T\) representing the number of datasets.

For each dataset:

• The first line contains an integer \(n\) indicating the number of towers.
• Each of the next \(n\) lines contains three integers \(x\), \(y\), and an energy parameter \(e\) (the energy parameter is provided but not used in the calculation).

All input is provided via standard input (stdin).

outputFormat

For each dataset, print a single line with the minimum total energy (rounded to the nearest integer) required to connect all towers.

Output is to be printed to standard output (stdout).

## sample

2
3
0 0 10
0 1 10
1 0 10
4
0 0 10
1 0 20
0 1 30
1 1 40

2
3