Q-44

#시간제한 생각 n=100,000
#->모든 두 행성 간의 거리 확인 방법 X -> x,y,z,각각 '좌표대로 정렬' 후 나열해서 간선을 만들면 최소 간선 수(답지 그림보고 이해) 
n=int(input())
parent=[0]*(n+1)
for i in range(1,n+1):
    parent[i]=i
edges=[]
result=0
def find_parent(parent,x):
    if parent[x]!=x:
        parent[x]=find_parent(parent,parent[x])
    return parent[x]
def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
x=[]
y=[]
z=[]
for i in range(1,n+1):
    data=list(map(int,input().split()))
    x.append((data[0],i))
    y.append((data[1],i))
    z.append((data[2],i))
x.sort()
y.sort()
z.sort()
for i in range(n-1):
    edges.append((x[i+1][0]-x[i][0],x[i][1],x[i+1][1]))
    edges.append((y[i+1][0]-y[i][0],y[i][1],y[i+1][1]))
    edges.append((z[i+1][0]-z[i][0],z[i][1],z[i+1][1]))
edges.sort()

for edge in edges:
    cost,a,b=edge
    if find_parent(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        result+=cost
print(result)
print(x)
print(edges)