#596. EMPIRE - Xây dựng đế chế

Một đế chế đang xây dựng mạng lưới cho các hành tinh trong nó. Đế chế gồm có hành tinh được biểu diễn như các điểm trong không gian chiều. Chi phí phải chi cho việc nối giữa hành tinh và hành tinh là với là tọa độ của hành tinh trong không gian chiều. Đế chế dự tính sẽ xây dựng cầu nối như vậy để các hành tinh liên thông với nhau và và chi phí phải chi phải nhỏ nhất có thể.

Dữ liệu vào:

• Dòng đầu là số hành tinh ;
• dòng sau mỗi dòng chứa ba số nguyên là tọa độ của một hành tinh.

Dữ liệu ra:

• Ghi trên một dòng một số duy nhất là chi phí nhỏ nhất có thể.

Ví dụ:

Dữ liệu vào:

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

Dữ liệu ra:

4

Giải thích:

• Nối giữa hành tinh và chi phí bằng ;
• Nối giữa hành tinh và chi phí bằng ;
• Nối giữa hành tinh và chi phí bằng ;
• Nối giữa hành tinh và chi phí bằng .

Tổng chi phí bằng .