(* 座標圧縮 *)
module CoordComp
  (* 座標の型 *)
  (Coord : sig
    type t
    val compare : t -> t -> int
  end) :
sig
  val compress :
    (* 座標のリスト *)
    Coord.t list ->
    (* 座標の数，圧縮する関数と解凍する関数を返す *)
    int * (Coord.t -> int) * (int -> Coord.t)
end = struct
  module IntMap = Map.Make (struct
    type t = int
    let compare = compare
  end)
  module CoordMap = Map.Make (Coord)

  let compress cs =
    let (n, comp, decomp) =
      List.fold_left (fun (n, comp, decomp) c ->
        if CoordMap.mem c comp then (n, comp, decomp)
        else (n + 1, CoordMap.add c n comp, IntMap.add n c decomp))
      (0, CoordMap.empty, IntMap.empty) cs in
    (n, (fun c -> CoordMap.find c comp), (fun n -> IntMap.find n decomp))
end

(* 配列版素集合データ構造 *)
module RawUnionFind : sig
  type t
  type class_

  (* n要素の素集合データ構造を作る *)
  val make : int -> t
  (* 要素がどの集合に属するか調べる *)
  (* 要素は0からn-1の整数である必要がある *)
  val find : t -> int -> class_
  (* 与えられた要素が属する集合同士を合併する *)
  val unite : t -> int -> int -> unit

  val compare_class : class_ -> class_ -> int
end = struct
  type t = { rank : int array; parent : int array }
  type class_ = int

  let make n =
    { rank = Array.make n 0;
      parent = Array.init n (fun c -> c) }

  let rec find uf x =
    if x = uf.parent.(x) then x
    else begin
      let y = find uf uf.parent.(x) in
      uf.parent.(x) <- y; y
    end

  let unite uf i j =
    let x = find uf i in
    let y = find uf j in
    if x <> y then begin
      if uf.rank.(x) < uf.rank.(y) then uf.parent.(x) <- y
      else begin
        uf.parent.(y) <- x;
        if uf.rank.(x) = uf.rank.(y) then
          uf.rank.(x) <- 1 + uf.rank.(x)
      end
    end

  let compare_class = compare
end

module WeightedGraph
  (Vertex : sig
    type t
    val compare : t -> t -> int
  end)
  (Weight : sig
    type t
    val compare : t -> t -> int
  end) :
sig
  (* 配列版の実装 *)
  val raw_kruskal :
    (* 頂点の数n *)
    int ->
    (* 辺のリスト *)
    (* 頂点は0からn-1までの整数でなくてはならない *)
    (int * int * Weight.t) list ->
    (* 最小全域木に含まれる辺のリスト *)
    (int * int * Weight.t) list

  (* 座標圧縮により，頂点に様々な型を使えるようにしたバージョン *)
  val kruskal :
    (* 辺のリスト *)
    (Vertex.t * Vertex.t * Weight.t) list ->
    (* 最小全域木に含まれる辺のリスト *)
    (Vertex.t * Vertex.t * Weight.t) list
end =
struct
  module CC = CoordComp (Vertex)

  let raw_kruskal n es =
    let uf = RawUnionFind.make n in
    List.fold_left (fun acc (u, v, w) ->
      if RawUnionFind.compare_class (RawUnionFind.find uf u) (RawUnionFind.find uf v) = 0
      then acc
      else begin
        RawUnionFind.unite uf u v;
        (u, v, w) :: acc
      end) [] (List.sort (fun (_, _, w) (_, _, w') -> Weight.compare w w') es)

  let kruskal es =
    let (n, comp, decomp) =
      CC.compress @@
        List.concat @@
          List.map (fun (u, v, _) -> [u; v]) es in
    List.map (fun (u, v, c) -> (comp u, comp v, c)) es
    |> raw_kruskal n
    |> List.map (fun (u, v, c) -> (decomp u, decomp v, c))
end
 
module Int = struct
  type t = int
  let compare = compare
end
 
module G = WeightedGraph (Int) (Int)
 
let () =
  let n = Scanf.scanf "%d\n" @@ fun n -> n in
  let xys = Array.to_list @@ Array.init n @@ fun i ->
    Scanf.scanf "%d %d\n" @@ fun x y -> x, y, i in
  let xedges =
    List.sort (fun (x, _, _) (x', _, _) -> compare x x') xys
    |> (fun ((x, y, i) :: xys) ->
        List.fold_left (fun (acc, x, y, i) (x', y', j) ->
          ((i, j, x' - x) :: acc, x', y', j)) ([], x, y, i) xys)
    |> (fun (acc, _, _, _) -> acc) in
  let yedges =
    List.sort (fun (_, y, _) (_, y', _) -> compare y y') xys
    |> (fun ((x, y, i) :: xys) ->
        List.fold_left (fun (acc, x, y, i) (x', y', j) ->
          ((i, j, y' - y) :: acc, x', y', j)) ([], x, y, i) xys)
    |> (fun (acc, _, _, _) -> acc) in
  List.rev_append xedges yedges
    |> G.raw_kruskal n
    |> List.map (fun (_, _, d) -> d)
    |> List.fold_left ( + ) 0
    |> Printf.printf "%d\n"


Measured memory_bytes: 38396