Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n,m=map(int,input().split())

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        temp=set([i])
        no_checked[i-1]=1
        while len(list(temp))>0:
            v=temp.pop()
            for item in xyz[v]:
                if no_checked[item-1]==0:
                    no_checked[item-1]=1
                    temp.add(item)
                    xyz[item].remove(v)
    #print(i,no_checked)
print(cnt)



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n,m=map(int,input().split())

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

def DFS(x):
    global no_checked
    global xyz
    no_checked[x-1]=1
    for item in xyz[x]:
        if no_checked[item-1]==0:
            DFS(item)

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        DFS(i)

    #print(i,no_checked)
print(cnt)
### BUGGY CODE ###

# 200216 C

import collections

N = int(input())
S = [""] * N
for i in range(N):
    S[i] = input()
c = collections.Counter(S)
cv = c.values()
ans = []
for i in c:
    if c[i] == max(cv):
        ans.append(i)
ans = sorted(ans)
for i in ans:
    print(i,end=" ")
print("")


### FIXED CODE ###

# 200216 C

import collections

N = int(input())
S = [""] * N
dic = {}
for i in range(N):
    S = input()
    if S in dic:
        dic[S] += 1
    else:
        dic[S] = 1

maxs = max(list(dic.values()))
ans = []
for i in dic:
    if dic[i] == maxs:
        ans.append(i)
ans = sorted(ans)
for i in ans:
    print(i,end=" ")
print("")
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())
n, = map(int,readline().split())
vw = [(0,0)]+[tuple(map(int,readline().split())) for _ in range(n)]

#print(vw)
A = 10
N = min(1<<A,n+1)

memo = [None for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = m
    #for j in range(1,L):
    #    memo[i][j] = max(memo[i][j],memo[i][j-1])


q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dic = [(0,0)]
    while u >= N:
        dic += [(vw[u][1]+w1,vw[u][0]+v1) for w1,v1 in dic]
        u >>= 1
    
    ans = 0
    for w,v in dic:
        if w <= l:
            ans = max(ans,memo[u][l-w]+v)
    print(ans)

        


### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())

n, = map(int,readline().split())
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

def merge(av,aw,bv,bw):
    la,lb = len(aw),len(bw)
    rv = [0]*(la+lb)
    rw = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb or (ia < la and aw[ia] < bw[ib]):
            rv[i] = av[ia]
            rw[i] = aw[ia]
            ia += 1
        else:
            rv[i] = bv[ib]
            rw[i] = bw[ib]
            ib += 1
    return rv,rw

A = 10
N = min(1<<A,n+1)
memov = [[] for _ in range(N)]
memow = [[] for _ in range(N)]

memov[0] = [0]
memow[0] = [0]

#from itertools import acumulate
for i in range(1,N):
    v,w = vw[i]
    m2v = [v+v1 for v1 in memov[i>>1]]
    m2w = [w+w1 for w1 in memow[i>>1]]
    memov[i],memow[i] = merge(memov[i>>1],memow[i>>1],m2v,m2w)

    #memov[i] = list(accumulate(memov[i],max))
    for j in range(1,len(memov[i])):
        memov[i][j] = max(memov[i][j-1],memov[i][j])
    
def solve(lstv,lstw,dv,dw,l):
    ans = 0
    idx = len(lstw)-1
    #print(lstv,lstw,dv,dw,l)
    for v,w in zip(dv,dw):
        while idx >= 0 and lstw[idx] + w > l:
            idx -= 1
        if idx >= 0 and v+lstv[idx] > ans:
            ans = v+lstv[idx]
    print(ans)        
 
 

q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dv = [0]
    dw = [0]
    while u >= N:
        v,w = vw[u]
        m2v = [v+v1 for v1 in dv]
        m2w = [w+w1 for w1 in dw]
        dv,dw = merge(dv,dw,m2v,m2w)
        u >>= 1
    
    #for j in range(1,len(dv)):
    #    dv[j] = max(dv[j-1],dv[j])
    
    solve(memov[u],memow[u],dv,dw,l)

#print(memov)
#print(memow)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    idx = [[] for _ in range(int(2e5+1))]
    for i in range(N):
        idx[A[i]].append(i)
    pos = 0
    empty = []
    visited = set()
    while pos == 0 or pos % N != 0:
        empty.append(pos)
        visited.add(pos % N)
        num = A[pos % N]
        nxt = bisect_right(idx[num], pos % N) % len(idx[num])
        npos = idx[num][nxt]
        while npos <= pos:
            npos += N
        pos = npos + 1
    goal = N * K % pos
    cur = empty[max(0, bisect_right(empty, goal) - 1)]
    #print(cur, goal)
    ans = []
    seen = set()
    while cur < goal:
        a = A[cur % N]
        if a not in seen:
            ans += [a]
            seen.add(a)
        else:
            seen.remove(a)
            i = len(ans) - 1
            while i > 0 and ans[i] != a:
                seen.remove(ans[i])
                i -= 1
            ans = ans[:i]
        cur += 1
    print(*ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left, bisect_right


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    idx = [[] for _ in range(int(2e5+1))]
    for i in range(N):
        idx[A[i]].append(i)
    pos = 0
    empty = []
    visited = set()
    while pos == 0 or pos % N != 0:
        empty.append(pos)
        visited.add(pos % N)
        a = A[pos % N]
        nxt = bisect_right(idx[a], pos % N) % len(idx[a])
        npos = idx[a][nxt] + (pos//N) * N
        if npos <= pos:
            npos += N
        pos = npos + 1
    goal = N * K % pos
    cur = empty[max(0, bisect_right(empty, goal) - 1)]
    #print(cur, goal)
    ans = []
    seen = set()
    while cur < goal:
        i = cur % N
        a = A[i]
        nxt = bisect_right(idx[a], cur % N) % len(idx[a])
        ncur = idx[a][nxt] + (cur//N) * N
        if ncur <= cur:
            ncur += N
        if ncur < goal:
            cur = ncur + 1
        else:
            ans += [a]
            cur = cur + 1
    print(*ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def dfs(ve, add):
  global seen
  global r
  seen[ve] = True
  r[ve] = add
  a = len(ki[ve])
  for i in range(a):
    b = ki[ve][i]
    if not seen[b]:
      dfs(b, add+ook[b])

N,Q = map(int, input().split())
side = [list(map(int, input().split())) for _ in range(N-1)]
op = [list(map(int, input().split())) for _ in range(Q)]
ki = [[] for _ in range(N)]
ook = [0]*N
seen = [False]*N
r = [0]*N

for i in range(N-1):
  a = side[i][0] -1
  b = side[i][1] -1
  ki[a].append(b)
  ki[b].append(a)
  
for i in range(Q):
  ook[op[i][0] -1] += op[i][1]
  
for i in range(N):
  if not seen[i]:
    dfs(i, ook[i])
    
print(" ".join(map(str,r)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(ve, add):
  global seen
  global r
  seen[ve] = True
  r[ve] = add
  a = len(ki[ve])
  for i in range(a):
    b = ki[ve][i]
    if not seen[b]:
      dfs(b, add+ook[b])

N,Q = map(int, input().split())
side = [list(map(int, input().split())) for _ in range(N-1)]
op = [list(map(int, input().split())) for _ in range(Q)]
ki = [[] for _ in range(N)]
ook = [0]*N
seen = [False]*N
r = [0]*N

for i in range(N-1):
  a = side[i][0] -1
  b = side[i][1] -1
  ki[a].append(b)
  ki[b].append(a)
  
for i in range(Q):
  ook[op[i][0] -1] += op[i][1]
  
for i in range(N):
  if seen[i]:
    continue
  dfs(i, ook[i])
    
print(" ".join(map(str,r)))
### BUGGY CODE ###

n = int(input())
map_ = {}

for i in range(n):
  a = int(input())
  
  if str(a) not in list(map_.keys()):
    map_.update({str(a):1})
  else:
    map_[str(a)] += 1
    map_[str(a)] %= 2
print(sum(map_.values()))

### FIXED CODE ###

n = int(input())
a_list = [int(input()) for _ in range(n)]

my_set = set()
for i in a_list:
  if i in my_set:
    my_set.remove(i)
  else:
    my_set.add(i)
print(len(my_set))
### BUGGY CODE ###

s = list(input())
q = int(input())

for i in range(q):
  tfc = input().split()
  if tfc[0] == '1':
    s.reverse()
  else:
    if tfc[1] == '1':
      s.insert(0, tfc[2])
    else:
      s.append(tfc[2])
for i in s:
  print(i, end='')

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
 
r = 0
for i in range(q):
  tfc = input().split()
  if tfc[0] == '1':
    r += 1
  else:
    if tfc[1] == '1':
      if r % 2 == 0:
        s.appendleft(tfc[2])
        #s.insert(0, tfc[2])
      else:
        s.append(tfc[2])
    if tfc[1] == '2':
     if r % 2 == 1:
        s.appendleft(tfc[2])
     else:
        s.append(tfc[2])          
if r % 2 == 0:
  for i in s:
      print(i, end='')
else:
  for i in (reversed(s)):
    print(i, end='')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    n,q = map(int,input().split())
    node = [[]for _ in range(n)]
    looked = [1]*n
    for i in range(n-1):
        a,b = map(int,input().split())
        node[b-1].append(a-1)
        node[a-1].append(b-1)
    counter = [0]*n
    for i in range(q):
        p,x = map(int,input().split())
        counter[p-1] += x
    queue = [0]
    looked[0] = 0
    while queue:
        now = queue.pop(0)
        for i in node[now]:
            if looked[i]:
                queue.append(i)
                counter[i] += counter[now]
                looked[i] = 0
    print(*counter)
main()

### FIXED CODE ###

#再帰のlimitを解除
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, q = map(int, input().split())
#何と繋がっているか（隣接リスト）
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

memo = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    memo[p] += x

#深さ優先探索 累積和
def dfs(v, par):
    for nv in g[v]:
        if nv == par:
            continue
        #1つ先に情報を流す
        memo[nv] += memo[v]
        #dfsを更新
        dfs(nv, v)

dfs(0, -1)

print(*memo)
### BUGGY CODE ###

# import queue
from collections import deque


# ★get input
h, w = map(int, input().split())

grid = [["" for i in range(w + 2)] for j in range(h + 2)]

for i in range(h):
    grid[i] = list(input())

    # 以下の様にsliceで取得することもできるが、パフォーマンスが若干落ちる。
    # 1000×1000件で50ミリ秒くらい差が出る?
    # line = input()
    # for j in range(w):
    #     grid[i][j] = line[j:j+1]


# ★exec
# BFSにて最短経路を求める
# 準備
distance = [[-1 for i in range(w)] for j in range(h)]
# que = queue.Queue()
que = deque()

# スタート地点の情報を設定
# 多点スタートの設定
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            # que.put((i, j))
            que.append((i, j))
            distance[i][j] = 0

# BFS開始
while len(que) > 0:

    # now = que.get()
    now = que.popleft()

    # 上下左右のマスを確認
    for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

        # 盤の範囲外なら何もしない
        target = (now[0] + move_y, now[1] + move_x)
        if not h > target[0] >= 0 or not w > target[1] >= 0:
            continue

        # 黒塗りされているなら何もしない
        # この条件、不要な気がする・・
        # if grid[target[0]][target[1]] == '#':
        #     continue

        # 距離が設定済みなら何もしない
        if not distance[target[0]][target[1]] == -1:
            continue

        # キューに追加
        # que.put(target)
        que.append(target)
        # 最短距離を設定
        distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

        # 黒塗り
        # この処理、不要な気がする・・
        # grid[target[0]][target[1]] = '#'

# 距離が最大の点 = 答えになる。
ans = 0
for i in range(h):
    ans = max(ans, max(distance[i]))

print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
c = sorted([r, g, b])[::-1]
ans = 0
for i in range(n // c[0] + 1):
    for j in range((n - i * r) // c[1] + 1):
        x = n - i * c[0] - j * c[1]
        if x >= 0 and x % c[2] == 0:
            ans += 1
print(ans)


### FIXED CODE ###

r, g, b, n = map(int, input().split())
c = sorted([r, g, b])[::-1]
ans = 0
for i in range(n // c[0] + 1):
    x = n - i * c[0]
    for j in range(x // c[1] + 1):
        y = x - j * c[1]
        if y < 0:
            break
        elif y % c[2] == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

s = input()[::-1]
 
sum_of_digits = 0
 
cnts = [0] * 2019
 
cnts[0] = 1
 
d = 1
 
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    
    cnts[sum_of_digits] += 1
 
ans = 0

for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)


### FIXED CODE ###

s = input()[::-1]
 
sum_of_digits = 0
 
cnts = [0] * 2019
 
cnts[0] = 1
 
d = 1
 
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1
 
ans = 0

for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
pq=[list(map(int,input().split())) for _ in range(m)]
ab=sorted(ab, key=lambda x:x[0])
pq=sorted(pq, key=lambda x:x[0])

res=[0 for _ in range(n)]
for p,q in pq:
	res[p-1]+=q
for a,b in ab:
	res[b-1]+=res[a-1]
res=[str(t) for t in res]
print(" ".join(res))


### FIXED CODE ###

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
pq=[list(map(int,input().split())) for _ in range(m)]
ab2=sorted(ab, key=lambda x:x[0])
pq2=sorted(pq, key=lambda x:x[0])

res=[0 for _ in range(n)]
for p,q in pq2:
	res[p-1]+=q
for a,b in ab2:
	res[b-1]+=res[a-1]
ans=str(res[0])
for i in range(1,n):
	ans+=" "+(str(res[i]))
print(ans)
### BUGGY CODE ###

from collections import deque

N = int(input())
Ass = deque(deque(map(int, input().split())) for _ in range(N))

dp = [0 for _ in range(N)]
index = [0 for _ in range(N)]
flag = True
cnt = 0
while flag:
    flag = False
    for i, As in enumerate(Ass):
        if index[i] >= N - 1:
            continue
        t = As[index[i]] - 1
        if index[t] >= N - 1:
            continue
        if Ass[t][index[t]] == i + 1:
            index[t] += 1
            index[i] += 1
            dp[t] = dp[i] = max(dp[t], dp[i]) + 1
            cnt += 1
            flag = True
if cnt != N * (N - 1) // 2:
    print(-1)
else:
    print(max(dp))


### FIXED CODE ###

from collections import deque
 
N = int(input())
Ass = tuple(deque(map(int, input().split())) for _ in range(N))
 
dp = [0 for _ in range(N)]
Q = set(range(N))
ans = -1
while Q:
    ans += 1
    Q2 = Q.copy()
    Q.clear()
    for i in Q2:
        if not Ass[i]:
            continue
        t = Ass[i][0] - 1
        if not Ass[t]:
            continue
        if Ass[t][0] == i + 1:
            Q.add(i)
            Q.add(t)
    for i in Q:
        Ass[i].popleft()

if any(Ass):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

from collections import Counter
from operator import mul
from functools import reduce
def combinations_count2(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

#
N=int(input())
A=list(map(int,input().split()))
#
hoge=Counter(A)
ans1=0
for i in hoge.values():
    if i==1:
        continue
    else:
        ans1+=combinations_count2(i,2)

for i in range(N):
    print(ans1-A.count(A[i])+1)



### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce
def combinations_count2(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

#
N=int(input())
A=list(map(int,input().split()))
#
hoge=Counter(A)
ans=0
for i in hoge.values():
    if i>=2:
        ans += combinations_count2(i, 2)
for i in range(N):
    print(ans-hoge[A[i]]+1)
### BUGGY CODE ###

import fractions
import math

def cf(x, y):
    cf = [1]
    for i in range(2, min(x,y)+1):
        if x % i == 0 and y % i == 0:
            cf.append(i)
    return cf

def comprime(a, b):
    return fractions.gcd(a, b) == 1

def is_prime(n):
    if n == 1 : return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

A,B = map(int, input().split())

y = cf(A,B)

so = [1]
cnt = 1
for i in range(1,len(y)-1):
    for j in range(len(so)):
        if comprime(y[i], so[j]) == False:
            break
    else:
        cnt += 1
        so.append(y[i])

print(cnt)


### FIXED CODE ###

from fractions import gcd
A,B = map(int, input().split())
g=gcd(A,B)
def prime_factorization(n):
    prime_num = []
    for i in range(2, int(n**.5)+1):
        num = 0
        while True:
            x,y = divmod(n, i)
            if y!= 0:
                break
            n = x
            num += 1
        if num>0:
            prime_num.append(i)
    if n > 1:
        prime_num.append(n)
    return prime_num
print(len(prime_factorization(g))+1)
### BUGGY CODE ###

p = 10 ** 9 + 7
N = 10 ** 7  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
	fact.append((fact[-1] * i) % p)
	inv.append((-inv[p % i] * (p // i)) % p)
	factinv.append((factinv[-1] * inv[-1]) % p)


n,a,b=map(int,input().split())
ans=((pow(2,N)-1)%(10**9+7)-cmb(n,a,p)-cmb(n,b,p))
print(int(ans))

### FIXED CODE ###

mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り
comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
 comb1*=i
 comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
 comb1*=pow(i,mod-2,mod)
 comb1%=mod
comb2=1
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
 comb2*=i
 comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
 comb2*=pow(i,mod-2,mod)
 comb2%=mod
ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)
### BUGGY CODE ###

def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

n, m, r = map(int, input().split())
R = list(map(int, input().split()))
R = [r_-1 for r_ in R]

d = [[float('inf') for i in range(n)] for j in range(n)]

for i in range(m):
  x, y, z = map(int, input().split())
  x, y = x-1, y-1
  d[x][y] = z
  d[y][x] = z
  
for i in range(n):
  d[i][i] = 0

d = warshal_floyd(d)

import itertools
ans = float('inf')
for p in itertools.permutations(R):
  q = 0
  for i in range(len(p)-1):
    q += d[p[i]][p[i+1]]
  if q <= ans:
    ans = q
print(ans)

### FIXED CODE ###

def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

n, m, r = map(int, input().split())
R = list(map(int, input().split()))
R = [r_-1 for r_ in R]

d = [[float('inf') for i in range(n)] for j in range(n)]

for i in range(m):
  x, y, z = map(int, input().split())
  x, y = x-1, y-1
  d[x][y] = z
  d[y][x] = z
  
for i in range(n):
  d[i][i] = 0

d = warshal_floyd(d)

import itertools
ans = float('inf')
for p in itertools.permutations(R):
  q = 0
  for i in range(len(p)-1):
    q += d[p[i]][p[i+1]]
  if q <= ans:
    ans = q
print(ans)
### BUGGY CODE ###

# ABC094 C - Many Medians
n = int(input())
x = list(map(int,input().split()))

for i in range(n):
    y = x[:]
    del y[i]
    y.sort()
    print(y[int((n/2)-1)])

### FIXED CODE ###

# ABC094 C - Many Medians
n = int(input())
x = list(map(int,input().split()))

y = sorted(x)
l = y[n//2 - 1]
r = y[n//2]
 
for x in x:
  print(l if x >= r else r)
### BUGGY CODE ###

import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    s,_ = sieve((10**6)+5)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        if Boo[i] and B[i]<500004:
            for j in range(i+1,lenb):
                if Boo[j] and s[B[j]-1]==False and B[j] % B[i] == 0:
                    Boo[j] = False

    cnt = 0
    for i in range(lenb):
        if Boo[i] and C[B[i]]==1:
            cnt += 1

    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    ZENBU = [False]*(10**6+4)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        temp = 2
        if ZENBU[B[i]]==False:
            while B[i]*temp < 1000002:
                ZENBU[B[i]*temp] = True
                temp+=1

    cnt = 0
    for i in range(lenb):
        if ZENBU[B[i]]==False and C[B[i]]==1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem B


def get_power(training_count):
    power = 1

    for i in range(1, training_count + 1):
        power *= i

    return power % (10 ** 9 + 7)


if __name__ == '__main__':
    training_count = int(input())

    print(get_power(training_count))


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem B


if __name__ == '__main__':
    from math import factorial

    training_count = int(input())
    print(factorial(training_count) % (10 ** 9 + 7))
### BUGGY CODE ###

import heapq
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort()
ans = 0
a = []
heapq.heapify(a)
for i in range(1,m+1):
  for j in range(len(ab)):
    if ab[j][0] == i:
      heapq.heappush(a,(-1)*ab[j][1])
  if a == []:
    continue
  else:
    x = heapq.heappop(a)
  ans += x
print(-ans)

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort()
queue = []
flag = 0
heapq.heapify(queue)
ans = 0
for i in range(1,m+1):
  for j in range(flag,n):
    if ab[j][0] <= i:
      heapq.heappush(queue,-ab[j][1])
      flag += 1
    else:
      break
  if queue != []:
    k = heapq.heappop(queue)
    ans += k
print(-ans)