from math import dist
import heapq as hq
from scipy.spatial import Delaunay  # Requires scipy

def bridge(pts):
    n = len(pts)
    if n <= 1:
        return 0
    
    # Compute Delaunay triangulation
    tri = Delaunay(pts)
    
    # Build graph from Delaunay edges
    adj = [[] for _ in range(n)]
    for simplex in tri.simplices:
        for i in range(3):
            u, v = simplex[i], simplex[(i + 1) % 3]
            if u < v:  # Avoid duplicates
                weight = dist(pts[u], pts[v])
                adj[u].append((v, weight))
                adj[v].append((u, weight))
    
    # Now run Prim's on this sparse graph
    pq = []
    visited = [False] * n
    res = 0
    hq.heappush(pq, (0, 0))
    
    while pq:
        wt, u = hq.heappop(pq)
        if visited[u]:
            continue
        res += wt
        visited[u] = True
        for v, weight in adj[u]:
            if not visited[v]:
                hq.heappush(pq, (weight, v))
    
    return res
pts = []
from random import randint
for i in range(5000):
    pts.append((randint(-500, 500), randint(-500, 500)))   

r = bridge(pts)
print(r)