CodeEff/ECCO huggingface dataset:
# Original solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2104

"""
import sys
from sys import stdin
from bisect import bisect_left
input = stdin.readline


def main(args):
    t = int(eval(input()))
    for _ in range(t):
        n, k = list(map(int, input().split()))
        houses = [int(x) for x in input().split()]

        if k >= n:              #  ????????¨?????????????????¨?????§??????
            print((0))
            continue


        diff = []
        prev = houses[0]
        for i, h in enumerate(houses[1:]):
            diff.append((h - prev, i))
            prev = h


        diff.sort(reverse=True)
        points = diff[:k-1]


        cable_total = 0
        prev = 0
        for _, p in points:
            cable_total += houses[p] - houses[prev]
            prev = p + 1
        if prev != (n - 1):
            cable_total += houses[-1] - houses[prev]

        print(cable_total)


if __name__ == '__main__':
    main(sys.argv[1:])

# Optimized solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2104
AC
"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    t = int(eval(input()))
    for _ in range(t):
        n, k = list(map(int, input().split()))
        houses = [int(x) for x in input().split()]

        if k >= n:              #  ????????¨?????????????????¨?????§????????´???
            print((0))
            continue

        # ??¶??????????????¢????¨????????????????????????¨????????????????????????
        gaps = []
        prev = houses[0]
        for i, h in enumerate(houses[1:]):
            gaps.append((h - prev, i))
            prev = h

        # gap?????§????????¨??????????????????????????????????????´????????????
        gaps.sort(reverse=True)
        gaps = gaps[:k-1]


        # ???????????????????????±????????????????¨??????????
        cable_total = 0
        prev = 0
        for _, p in gaps:
            cable_total += houses[p] - houses[prev]
            prev = p + 1
        if prev != (n - 1):
            cable_total += houses[-1] - houses[prev]

        print(cable_total)


if __name__ == '__main__':
    main(sys.argv[1:])
# Original solution
from operator import itemgetter
import heapq
def prim_heap():
  used=[True]*n
  edgelist=[]
  for e in edge[0]:
    heapq.heappush(edgelist,e)
  used[0] = False
  res = 0
  while len(edgelist) != 0:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,e)
    res += minedge[0]
  return res

import sys
input=sys.stdin.readline
n=int(eval(input()))
l=[list(map(int,input().split())) for i in range(n)]
edge=[[] for i in range(n)]
l.sort()
for i in range(n):
  l[i]=[l[i][0],l[i][1],i]
for i in range(n-1):
  edge[i].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i+1])
  edge[i+1].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i])
l=sorted(l,key=itemgetter(1))
for i in range(n-1):
  edge[l[i][2]].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i+1][2]])
  edge[l[i+1][2]].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i][2]])
print((prim_heap()))

# Optimized solution
from operator import itemgetter
import heapq
def prim_heap():
  used=[True]*n
  edgelist=[]
  for e in edge[0]:
    heapq.heappush(edgelist,e)
  used[0] = False
  res = 0
  while len(edgelist) != 0:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,e)
    res += minedge[0]
  return res

import sys
input=sys.stdin.readline
n=int(eval(input()))
l=[list(map(int,input().split())) for i in range(n)]
edge=[[] for i in range(n)]
l.sort()
for i in range(n):
  l[i]=[l[i][0],l[i][1],i]
for i in range(n-1):
  edge[i].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i+1))
  edge[i+1].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i))
l=sorted(l,key=itemgetter(1))
for i in range(n-1):
  edge[l[i][2]].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i+1][2]))
  edge[l[i+1][2]].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i][2]))
print((prim_heap()))
# Original solution
n = int(eval(input()))
x = []
y = []
for i in range(n):
    s = list(map(int, input().split()))
    x.append([s[0], i])
    y.append([s[1], i])

x.sort()
y.sort()

xdiff = []
ydiff = []
for i in range(1, n):
    xdiff.append([x[i][0] - x[i - 1][0], x[i - 1][1], x[i][1]])
    ydiff.append([y[i][0] - y[i - 1][0], y[i - 1][1], y[i][1]])

xdiff.sort()
ydiff.sort()

parent = [-1] * n

def getParent(index):
    while parent[index] != -1:
        index = parent[index]

    return index

count = 0
ans = 0
xIndex = 0
yIndex = 0
while count != n - 1:
    if xIndex != n - 1:
        xTemp = xdiff[xIndex]
    if yIndex != n - 1:
        yTemp = ydiff[yIndex]

    if yIndex == n - 1 or (xIndex != n - 1 and xTemp[0] < yTemp[0]):
        xIndex += 1
        temp = xTemp
    else:
        yIndex += 1
        temp = yTemp

    parent1 = getParent(temp[1])
    parent2 = getParent(temp[2])
    if parent1 == parent2:
        continue
    else:
        count += 1
        ans += temp[0]
        parent[parent1] = parent2

print(ans)

# Optimized solution
import sys
sys.setrecursionlimit(100000)
n = int(eval(input()))
x = []
y = []
for i in range(n):
    s = list(map(int, input().split()))
    x.append([s[0], i])
    y.append([s[1], i])

x.sort()
y.sort()

xdiff = []
ydiff = []
for i in range(1, n):
    xdiff.append([x[i][0] - x[i - 1][0], x[i - 1][1], x[i][1]])
    ydiff.append([y[i][0] - y[i - 1][0], y[i - 1][1], y[i][1]])

xdiff.sort()
ydiff.sort()

parent = [-1] * n

def getParent(index):
    if parent[index] == -1:
        return index
    else:
        parent[index] = getParent(parent[index])
        return parent[index]

count = 0
ans = 0
xIndex = 0
yIndex = 0
while count != n - 1:
    if xIndex != n - 1:
        xTemp = xdiff[xIndex]
    if yIndex != n - 1:
        yTemp = ydiff[yIndex]

    if yIndex == n - 1 or (xIndex != n - 1 and xTemp[0] < yTemp[0]):
        xIndex += 1
        temp = xTemp
    else:
        yIndex += 1
        temp = yTemp

    parent1 = getParent(temp[1])
    parent2 = getParent(temp[2])
    if parent1 == parent2:
        continue
    else:
        count += 1
        ans += temp[0]
        parent[parent1] = parent2

print(ans)
# Original solution
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(eval(input()))
l=sorted([tuple(map(int,input().split())) for i in range(n)])
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort()
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)

# Optimized solution
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(eval(input()))
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:x[0])
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort(key=lambda x:x[0])
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)
# Original solution
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(eval(input()))
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:x[0])
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort(key=lambda x:x[0])
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)

# Optimized solution
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(eval(input()))
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort()
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort(key=lambda x:x[0])
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)
# Original solution
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(eval(input()))
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort()
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort(key=lambda x:x[0])
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)

# Optimized solution
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(eval(input()))
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort()
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort()
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)
# Original solution
import heapq
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(eval(input()))
town = [list(map(int,input().split()))+[i] for i in range(N)]

townx = sorted(town)
towny = sorted(town,key = lambda t : t[1])

heap = []
heapq.heapify(heap)

for i in range(N-1):
    heapq.heappush(heap,[abs(townx[i][0]-townx[i+1][0]),townx[i][2],townx[i+1][2]])
    heapq.heappush(heap,[abs(towny[i][1]-towny[i+1][1]),towny[i][2],towny[i+1][2]])

uf = UnionFind(N)
ans = 0

while heap:
    cost,t1,t2 = heapq.heappop(heap)
    if uf.same(t1,t2):
        continue
    uf.union(t1,t2)
    ans += cost
print(ans)


# Optimized solution
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(eval(input()))
town = [list(map(int,input().split()))+[i] for i in range(N)]

townx = sorted(town)
towny = sorted(town,key = lambda t : t[1])

road = []

for i in range(N-1):
    road.append([abs(townx[i][0]-townx[i+1][0]),townx[i][2],townx[i+1][2]])
    road.append([abs(towny[i][1]-towny[i+1][1]),towny[i][2],towny[i+1][2]])

road.sort()

uf = UnionFind(N)
ans = 0

for r in road:
    cost,t1,t2 = r
    if uf.same(t1,t2):
        continue
    uf.union(t1,t2)
    ans += cost
    
print(ans)
# Original solution
with open(0) as f:
    N, *xy = list(map(int, f.read().split()))
from collections import namedtuple
v = namedtuple('v',['x','y'])
V = [v(x-1,y-1) for x,y in zip(xy[::2],xy[1::2])] #頂点
cost = lambda i,j:min(abs(V[i].x-V[j].x), abs(V[i].y-V[j].y))
from itertools import combinations 
Edge = sorted([(cost(i,j), i, j) for i,j in combinations(list(range(N)),2)])
root = namedtuple('root',['num', 'rank']) #(num_of_root, rank_of_root)
Root = [root(i,0) for i in range(N)] 

def fr(i): #findRoot
    if i == Root[i].num:
        return Root[i]
    Root[i] = fr(Root[i].num)
    return Root[i]


def unionT(i, j): #unionTree
    p, q = fr(i), fr(j)
    if p.rank < q.rank:
        Root[p.num] = q
    elif p.rank > q.rank:
        Root[q.num] = p
    elif p.rank == q.rank:
        r, s = min(p, q), max(p, q)
        Root[r.num] = Root[s.num] = root(r.num, r.rank+1)
    

ans = 0
#最小全域木の大きさ算出(環状にならないように辺を小さい順に足してゆく)
for w, i, j in Edge:
    p, q = fr(i), fr(j)
    if p.num == q.num: #既に連結済み
        continue
    else:
        unionT(i,j)
        ans += w
print(ans)

# Optimized solution
with open(0) as f:
    N, *xy = list(map(int, f.read().split()))

from collections import namedtuple
v = namedtuple('v',['coordinate','num'])
#最小全域木に使われる辺は高々座標(xまたはy)が隣接する頂点間のものである
#したがって、x座標・y座標それぞれでソートして辺を求める
X = sorted([v(x,i) for x,i in zip(xy[::2], list(range(N)))])
Y = sorted([v(y,i) for y,i in zip(xy[1::2], list(range(N)))])

diffiter = lambda X:list(zip(X[:len(X)-1], X[1:])) #Xの1階階差差分のイテレータを返す関数
cost = lambda u,v:abs(u.coordinate - v.coordinate)
from itertools import chain
Edge = sorted([(cost(u,v), u.num, v.num) for u,v in chain(diffiter(X),diffiter(Y))])

root = namedtuple('root',['num', 'rank']) #(num_of_root, rank_of_root)
Root = [root(i,0) for i in range(N)]

def fr(i): #findRoot
    if i == Root[i].num:
        return Root[i]
    Root[i] = fr(Root[i].num)
    return Root[i]


def unionT(i, j): #unionTree
    p, q = fr(i), fr(j)
    if p.rank < q.rank:
        Root[p.num] = q
    elif p.rank > q.rank:
        Root[q.num] = p
    elif p.rank == q.rank:
        r, s = min(p, q), max(p, q)
        Root[r.num] = Root[s.num] = root(r.num, r.rank+1)
    

ans = 0
#最小全域木の大きさ算出(環状にならないように辺を小さい順に足してゆく)
for w, i, j in Edge:
    if fr(i).num == fr(j).num: #既に連結済み
        continue
    else:
        unionT(i,j)
        ans += w
print(ans)
# Original solution
N = int(eval(input()))
P = [[i, list(map(int, input().split()))] for i in range(N)]

X = sorted([[i, xy[0]] for i, xy in P], key=lambda x: x[1])
Y = sorted([[i, xy[1]] for i, xy in P], key=lambda y: y[1])

Xe = [[X[i][0], X[i+1][0], abs(X[i][1]-X[i+1][1])] for i in range(N-1)]
Ye = [[Y[i][0], Y[i+1][0], abs(Y[i][1]-Y[i+1][1])] for i in range(N-1)]
E = sorted(Xe + Ye, key=lambda e: e[2])


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


uf = UnionFind(N)
edge_cnt = 0
MST_cost = 0
i = 0

while edge_cnt < N-1:
    a, b, cost = E[i]
    if not uf.same_check(a, b):
        MST_cost += cost
        uf.union(a, b)
        edge_cnt += 1
    i += 1

print(MST_cost)

# Optimized solution
N = int(eval(input()))
Points = [[i] + list(map(int, input().split())) for i in range(N)]

# x, yそれぞれについてソートして、一番近いところを見れば十分
Edges = []
Points.sort(key=lambda p: p[1])
for i in range(N - 1):
    n1, x1, y1 = Points[i]
    n2, x2, y2 = Points[i + 1]
    Edges.append([n1, n2, x2 - x1])

Points.sort(key=lambda p: p[2])
for i in range(N - 1):
    n1, x1, y1 = Points[i]
    n2, x2, y2 = Points[i + 1]
    Edges.append([n1, n2, y2 - y1])


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


uf = UnionFind(N)
Edges.sort(key=lambda e: e[2], reverse=True)
MST_cost = 0
i = 0

# 辺のコストが小さいものから、閉路を作らないように、木を構成する
# 最小全域木の必要辺は(頂点数-1)本
while i != N - 1:
    x, y, cost = Edges.pop()
    # 同じ辺集合に属していないならば（閉路が生まれないならば）
    if not uf.same_check(x, y):
        MST_cost += cost
        uf.union(x, y)
        i += 1

print(MST_cost)