문제풀이

import sys, math
input = sys.stdin.readline

# 루트 노드 찾기 함수
def find(p, x):
    if p[x] != x:
        p[x] = find(p, p[x])
    return p[x]

# 두 노두 루트 노드 작은 수로 합치기
def union(p, a, b):
    a = find(p, a)
    b = find(p, b)
    if a < b:
        p[b] = a
    else:
        p[a] = b

n = int(input())                            # 노두 갯수 입력
parent = [i for i in range(n+1)]            # 부모 테이블 초기화
stars = [0]                                 # 0번 인덱스 버림 별좌표 입력 받을 리스트

for i in range(1, n+1):
    x, y = map(float, input().split())
    stars.append((i, x, y))                 # 노드 번호와 좌표를 리스트에 삽입

dist = []                                   # 별 사이 거리(간선) 받을 리스트
for i in range(1, n):                       # 별 사이 간 거리를 하나씩 비교해 피타고라스 정리로 거리 구하기
    for j in range(i+1, n+1):
        cost = math.sqrt(abs(stars[i][1]-stars[j][1]) ** 2 + abs(stars[i][2]-stars[j][2]) ** 2)
        dist.append((cost, i, j))           # 별 사이 거리와 연결된 노드 두개 삽입
dist.sort()                                 # 거리로 오름차순 정렬

result = 0                                          # 총 비용 계산 결과 담을 변수
for i in dist:                                      # 거리가 짧은 순서대로
    if find(parent, i[1]) != find(parent, i[2]):    # 루트노드가 같지 않은 노드들에 대해(사이클이 없는 노드)
        union(parent, i[1], i[2])                   # 합치기
        result += i[0]                              # 총 비용 누적
print(result)                                       # 결과 출력

# 특정 원소가 속한 집합을 찾기
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

# 노드의 개수와 간선(union 연산)의 개수 입력받기
n = int(input())
m = int(input())

parent = [0] * (n + 1) # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, n + 1):
	parent[i] = i

# 모든 간선에 대한 정보를 입력
for _ in range(m):
	a, b, cost = map(int, input().split())
	# 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
	edges.append((cost, a, b))

# 간선을 비용순으로 정렬
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)