## COCI '09 Contest 7 #4 Svemir

View as PDF

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type

Fourth Great and Bountiful Human Empire is developing a transconduit tunnel network connecting all it's 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 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