Fourth Great and Bountiful Human Empire is developing a transconduit
tunnel network connecting all its planets. The Empire consists of
planets, represented as points in the 3D space. The cost of forming a
transconduit tunnel between planets
and
is:
where are 3D coordinates of planet
, and
are coordinates of planet
. The Empire needs to build
exactly
tunnels in order to fully connect all planets, either by
direct links or by a chain of links. You need to come up with the lowest
possible cost of successfully completing this project.
Input Specification
The first line of input contains one integer
, number of planets.
The next lines contain exactly
integers each. All integers are
between
and
inclusive. Each line contains the
,
,
and
coordinate of one planet (in order).
No two planets will occupy the exact same point in space.
Output Specification
The first and only line of output should contain the minimal cost of forming the network of tunnels.
Sample Input 1
2
1 5 10
7 8 2
Sample Output 1
3
Sample Input 2
3
-1 -1 -1
5 5 5
10 10 10
Sample Output 2
11
Sample Input 3
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
Sample Output 3
4
Comments