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

from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()


def check(x):
    # k番目の数がx以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    for i in range(n):
        if a[i] > 0:
            idx = bisect_right(a, x // a[i])
            cnt += max(idx - i - 1, 0)
        elif a[i] < 0:
            idx = bisect_left(a, -(x // abs(a[i])))
            # cnt += n - idx
            cnt += n - max(idx, i + 1)
        else:
            # a[i] == 0
            if x >= 0:
                cnt += n - i - 1

        if cnt >= k:
            return True
    # print('check', x, cnt)
    return cnt >= k


lb = -10**19  # False
ub = +10**19  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    # print(lb, ub)
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

a_minus = a_zero = a_plus = 0
for i in range(n):
    if a[i] > 0:
        a_plus += 1
    elif a[i] == 0:
        a_zero += 1
    else:
        a_minus += 1

aa_minus = a_minus * a_plus
aa_zero = a_zero * (n - a_zero) + a_zero * (a_zero - 1) // 2


def check_minus(x):
    # k番目の数がx(<0)以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    j = a_minus + a_zero
    for i in range(a_minus):
        # a[i] < 0
        while j < n and a[i] * a[j] > x:
            j += 1
        cnt += n - j

    return cnt >= k


def check_plus(x):
    # k番目の数がx(>0)以下であるか
    # x以下の数字がk個以上あるか

    def func(b, m):
        # 昇順ソート済みの数列b (長さm)
        # 掛け算してx以下となる数を求める
        c = 0
        j = m - 1
        for i in range(m):
            while j > 0 and b[i] * b[j] > x:
                j -= 1
            c += max(j - i, 0)
        return c

    cnt = aa_minus + aa_zero
    cnt += func(a[-a_plus:], a_plus)
    cnt += func(list(reversed(a[:a_minus])), a_minus)
    return cnt >= k


if k <= aa_minus:
    # k番目の数は負の数
    lb = a[0] * a[-1] - 1  # False
    ub = 0  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_minus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub
elif k <= aa_minus + aa_zero:
    # k番目の数は0
    ans = 0
else:
    # k番目の数はプラス
    lb = 0  # False
    ub = max(a[0]**2, a[-1]**2) + 1  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_plus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub

print(ans)
### BUGGY CODE ###

import itertools

N = int(input())
for n in range(1,N+1):
    if n < 6:
        print(0)
    else:
        #M =int((n-2)**0.5)
        count = 0
        for x in range(1,101):
            for y in range(1,x+1):
                for z in range(1,y+1):
                    if (x+y)*(x+z)+y**2+z**2 == n:
                        if x == y == z:
                            count = 1
                        elif x == y or y == z:
                            count = 3
                        else:
                            count = 6
                        #p=[x,y,z]
                        #q=[]
                        #for p in itertools.permutations(p):
                            #q.append(p)
                            #count = len(set(q))
                    else:
                        pass
        print(count)



### FIXED CODE ###

N = int(input())
lst = [0]*(N+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            p = (x+y)*(x+z)+y**2+z**2
            if p > N:
                break
            else:
                lst[p] += 1
for i in range(1,N+1):
    print(lst[i])
### BUGGY CODE ###

sel='D'

if sel=='A':
    S=input()
    if S[2]==S[3] and S[4]==S[5]:
        print('Yes')
    else:
        print('No')

if sel=='B':
    X=int(input())
    ans=0
    ans+=(X//500)*1000
    ans+=((X%500)//5)*5
    print(ans)

if sel=='C':
    K,N=map(int,input().split())
    A=[int(i) for i in input().split()]
    d=[A[0]+K-A[-1]]
    for i in range(N-1):
        d.append(A[i+1]-A[i])
    d.sort()
    print(K-d[-1])

if sel=='D':
    N,X,Y=map(int,input().split())
    cnt={}
    for k in range(1,N):
        cnt[k]=0
    for i in range(1,N):
        for j in range(i+1,N+1):
            k=j-i # まっすぐ
            k=min(k,abs(i-X)+1+abs(j-Y)) # う回路１
            k=min(k,abs(i-Y)+1+abs(X-j)) # う回路２
            cnt[k]+=1

    for k in range(1,N):
        print(cnt[k])





### FIXED CODE ###

sel='D'

if sel=='A':
    S=input()
    if S[2]==S[3] and S[4]==S[5]:
        print('Yes')
    else:
        print('No')

if sel=='B':
    X=int(input())
    ans=0
    ans+=(X//500)*1000
    ans+=((X%500)//5)*5
    print(ans)

if sel=='C':
    K,N=map(int,input().split())
    A=[int(i) for i in input().split()]
    d=[A[0]+K-A[-1]]
    for i in range(N-1):
        d.append(A[i+1]-A[i])
    d.sort()
    print(K-d[-1])

if sel=='D':
    N,X,Y=map(int,input().split())
    cnt={}
    for k in range(1,N):
        cnt[k]=0
    for i in range(1,N):
        for j in range(i+1,N+1):
            k=j-i # まっすぐ
            k=min(k,abs(i-X)+1+abs(j-Y)) # う回路１
            k=min(k,abs(i-Y)+1+abs(X-j)) # う回路２
            cnt[k]+=1

    for k in range(1,N):
        print(cnt[k])
### BUGGY CODE ###

import numpy as np
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
A = list(map(int, input().split()))

# kごとに、
# 異なる数がいくつあるかを調べる
# (2以上要素が存在する)異なる数ごとに、
# (要素数)C2を解く。

np_A = np.array(A)

# 辞書作成
dic = {}

for k in range(N):
    before = A[:k]
    after = A[k+1:]

    before.extend(after)
    tmp_k = np.array(before)
    # print("tmp_k", tmp_k)   # k以上
    # print(np.unique(np_A))

    # 同じ組み合わせのケースを排除する。
    # (num, 要素数)の組み合わせを辞書かで作る
    # →単純にnCrなら(n, r)で保存する

    k_unique = np.unique(tmp_k)
    ans = 0

    for u in k_unique:
        count_u = np.count_nonzero(tmp_k==u)
        if count_u < 2:
            continue
        key = "{0}".format(count_u) + "2"   # key
        if key in dic.keys():
            ans += dic[key]
            continue

        # (count_u) C 2
        tmp = int(count_u*(count_u-1)/2)
        ans += tmp
        # 値の更新
        dic[key] = tmp
    
    print(ans)


### FIXED CODE ###

import numpy as np
from collections import Counter


N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
np_A = np.array(A)

# 全体を求める
tmp_all = np.array(A)
unique = np.unique(tmp_all)
# print("unique:", unique)
ans_all = 0
for u in unique:
    count_u = c[u]
    # print(f"u:{u}, count_u:{count_u}")
    if count_u < 2:
        continue
    # (count_u) C 2
    tmp = int(count_u*(count_u-1)/2)
    ans_all += tmp
# print("all", ans_all)


# kごとのケースを求めて、全体から引く
for i in A:
    print(ans_all - c[i] + 1)
### BUGGY CODE ###

H, W, D=[int(x) for x in str(input()).split()]
A=[[0 for x in range(W+1)]]
for i in range(1,H+1):
  b=[0]
  b+=[int(x) for x in str(input()).split()]
  A.append(b)
Q=int(input())
LR=[[0 for x in range(3)]]
for i in range(1,Q+1):
  b=[0]
  b+=[int(x) for x in str(input()).split()]
  LR.append(b)



B=[0 for x in range(H*W+1)]
for i in range(1,W+1):
  for j in range(1,H+1):
    B[A[j][i]]=[j,i]
ans=[]
for i in range (1,Q+1):
  s=0
  x=LR[i][1]
  while x!=LR[i][2]:
    s+=abs(B[x][0]-B[x+D][0])+abs(B[x][1]-B[x+D][1])
    x+=D
  ans.append(s)
for i in ans:
  print(i)


### FIXED CODE ###

H, W, D=[int(x) for x in str(input()).split()]
A=[[0 for x in range(W+1)]]
for i in range(1,H+1):
  b=[0]
  b+=[int(x) for x in str(input()).split()]
  A.append(b)
Q=int(input())
LR=[[0 for x in range(3)]]
for i in range(1,Q+1):
  b=[0]
  b+=[int(x) for x in str(input()).split()]
  LR.append(b)












B=[0 for x in range(H*W+1)]
for i in range(1,W+1):
  for j in range(1,H+1):
    B[A[j][i]]=[j,i]

XY=[0]
for i in range(1,D+1):

  C=[]
  x=i
  s=0
  while x<(H*W-D+1):

    s+=abs(B[x][0]-B[x+D][0])+abs(B[x][1]-B[x+D][1])
    C.append(s)
    x+=D

  C.append(s+abs(B[i][0]-B[x][0])+abs(B[i][1]-B[x][1]))
  XY.append(C)


def mo(x,y):
  if x%y==0:
    return y
  else:
    return x%y

def br(x):
  if x<=0:
    return 0
  else:
    return int(x)

ans=[]
for i in range (1,Q+1):
  if LR[i][1]<LR[i][2] and LR[i][1]==mo(LR[i][1],D):
    g=XY[mo(LR[i][1],D)][br((LR[i][1]-0.1)//D-1)]
    h=XY[mo(LR[i][1],D)][br((LR[i][2]-0.1)//D-1)]

    ans.append(h)
  elif LR[i][1]<LR[i][2]:
    g=XY[mo(LR[i][1],D)][br((LR[i][1]-0.1)//D-1)]
    h=XY[mo(LR[i][1],D)][br((LR[i][2]-0.1)//D-1)]

    ans.append(h-g)
  elif LR[i][1]>LR[i][2]:
    g=XY[mo(LR[i][2],D)][br((LR[i][2]+0.1)//D)-2]
    h=XY[mo(LR[i][2],D)][-1]-XY[mo(LR[i][1],D)][br((LR[i][2]+0.1)//D-2)]
    ans.append(h+g)
  else:
    ans.append(0)

for i in ans:
  print(i)
### BUGGY CODE ###


n = int(input())
l = list(map(int, input().split()))
res = 1
flag = 0
for i in l:
	res *= i
	if i == 0:
		flag = 0
		res = 0
	if(res > 1000000000000000000):
		flag = 1
if flag == 1:
	print('-1')
else : print(res)


### FIXED CODE ###


n = int(input())
l = list(map(int, input().split()))
res = 1
flag = 0
for i in l:
	res *= i
	if i == 0:
		flag = 0
		res = 0
	if(res > 1000000000000000000):
		flag = 1
		break
for i in l:
	if (i == 0):
		flag = 0
		res = 0
if flag == 1:
	print('-1')
else : print(res)
### BUGGY CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
new_search_index=list(range(1,N+1))
for answer in range(1,N**3):
  matched_flag=[False]*(N+1)

  search_index=new_search_index;
  new_search_index=[]
  #print(search_index)
  for i in search_index:
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      new_search_index.append(i)
      new_search_index.append(ai_next)
  
  if len(new_search_index)==0:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()


### FIXED CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3):
  if N>900 and answer>3000:
    print(N*(N-1)//2)
    sys.exit()
  
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()
### BUGGY CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**18
def solve(N,A):
    P = set()

    for i in range(N):
        n = A[i]
        if n % 2 == 0 and 2 in P: break
        while n % 2 == 0:
            P.add(2)
            n //= 2
            
        f = 3
        while f * f <= n:
            if n % f == 0:
                if f in P: break
                P.add(f)
                while n%f == 0:
                    n //= f
            else:
                f += 2
        else:
            if n != 1:
                if n in P: break
                P.add(n)
            
            continue
        break
    else:
        return 0
        
    return 1 



def main():
    N=ii()
    A=np.array(list(mi()))

    flag = solve(N,A)
    if flag == 0:
        print("pairwise coprime")
    else:
        gcd = np.gcd.reduce(A)
        if gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")
       

if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**18
def solve(N,A):
    P = set()

    fl = True
    for i in range(N):
        n = A[i]
        if n % 2 == 0 and 2 in P: 
            fl = False
            break
        while n % 2 == 0:
            P.add(2)
            n //= 2
            
        f = 3
        while f * f <= n:
            if n % f == 0:
                if f in P: 
                    fl = False
                    break
                
                P.add(f)
                while n % f == 0:
                    n //= f
            else:
                f += 2

        if n != 1:
            if n in P:
                fl = False
                break
            P.add(n)
            
        if not fl:
            break

        
    return fl



def main():
    N=ii()
    A=np.array(list(mi()))

    flag = solve(N,A)
    if flag:
        print("pairwise coprime")
    else:
        gcd = np.gcd.reduce(A)
        if gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")
       

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('solve', '(i8,i8[:])')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()
### BUGGY CODE ###

import math
n,l =  input() , [ q-p for p,q in enumerate([ i for i,j in enumerate( map( int , input().split())) if i+1 == j ] ) ]
print( sum( [ math.ceil(l.count(j)/2) for i,j in enumerate(l) if i==0  or l[i]!=l[i-1]]))

### FIXED CODE ###

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

#入れ替える必要のある要素のインデントを格納
l = []
for i,item in enumerate(m):
  if i+1 == item:
    l.append(i)

ans = len(l)

for i in range(len(l)):
  if i == 0:
    continue

  if l[i] == l[i-1] + 1:
    ans -= 1
    l[i] = l[i-1] - 1


print(ans)
### BUGGY CODE ###

N=int(input())
S=input()

D=[0]*1000

for i in range(1000):
    a=str(i//100)
    b=str((i//10)%10)
    c=str(i%10)
    f=0
    for j in S:
        if(f==2 and c==j):
            D[i]=1
            break
        elif(f==1 and b==j):
            f=2
        elif(f==0 and a==j):
            f=1
print(sum(D))



### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for a in range(10):
  for b in range(10):
    for c in range(10):
      a, b, c = str(a), str(b), str(c)
      a_find = s.find(a)
      if a_find == -1:
        continue
      b_find = s.find(b, a_find + 1)
      if b_find == -1:
        continue
      c_find = s.find(c, b_find + 1)
      if c_find == -1:
        continue
      ans += 1
print(ans)
### BUGGY CODE ###

N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]

e=[[True]*N for _ in range(N)]
ans=0
for k in range(N):
  for i in range(N):
    for j in range(N):
      if A[i][j] > A[i][k] + A[k][j]:
        print(-1)
        exit()
      elif (A[i][j]==A[i][k]+A[k][j]) and (A[i][k]!= 0) and (A[k][j]!= 0):
        e[i][j]=False

ans=0
for i in range(N):
  for j in range(N):
    if e[i][j]: ans+=A[i][j]

print(ans//2)

### FIXED CODE ###

import numpy as np
 
N = int(input())
A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N,N)

np.fill_diagonal(A, 10**9+1)

ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    d = np.min(A[i]+A[j])
    if d > A[i][j]:
      ans+=A[i][j]
    elif d < A[i][j]:
      print(-1)
      exit()

print(ans)
### BUGGY CODE ###

import re
import numpy as np
_, q = input().split()
s = input()
qs = [list(map(int, input().split())) for _ in range(int(q))]

def get_num_AC(s):
    count = len(re.split(r'AC', s)) - 1
    return count

def get_substr(s, smaller, larger):
    s1 = s[smaller-1:larger]
    return s1

for smaller, larger in qs:
    substr = get_substr(s, smaller, larger)
    count = get_num_AC(substr)
    print(count)


### FIXED CODE ###

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

s = input()

count = [0] * n

for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        count[i] += 1

from itertools import accumulate

accum = list(accumulate(count))

for _ in range(q):
    l, r = map(int, input().split())
    print(accum[r-1] - accum[l-1])
### BUGGY CODE ###

n, k = [int(_) for _ in input().split()]
h = [int(_) for _ in input().split()]
mc = [0]
for i in range(1,n):
    ans = 1e9
    for j in range(max(i-k, 0), i):
        ans = min(ans, mc[j]+abs(h[i]-h[j]))
    mc.append(ans)
print(ans)

### FIXED CODE ###

n, k = [int(_) for _ in input().split()]
h = [int(_) for _ in input().split()]
mc = [0]
for i in range(1,n):
    ans = 1e9
    for j in range(max(i-k, 0), i):
        ans = min(ans, mc[j]+abs(h[i]-h[j]))
    mc.append(ans)
print(ans)
### BUGGY CODE ###

def scoring():
    score = 0
    last = [0] * 26
    for d in range(len(out)):
        last[out[d]] = d + 1
        score += S[d][out[d]]
        score -= sum((d + 1 - l) * c for l, c in zip(last, C))
    return score

def local_search(d, q, score):
    # old = out[d]
    out[d] = q
    tmp = scoring()
    # if tmp > score:
        # score = tmp
    # else:
        # out[d] = old
    return tmp

D = int(input())
C = list(map(int, input().split()))
S = []
for _ in range(D):
    s = list(map(int, input().split()))
    S.append(s)
out = [int(input()) - 1 for _ in range(D)]
res = scoring()
M = int(input())
for _ in range(M):
    d, q = map(int, input().split())
    res = local_search(d-1, q-1, res)
    print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def scoring(sc):
    last = [0] * 26
    res = 0
    penalty = 0
    for i in range(D):
        t = out[i]
        res += S[i][t]
        penalty += sc - (i + 1 - last[t]) * C[t]
        res -= penalty
        last[t] = i + 1
    return res

D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(D)]
out = [int(input()) - 1 for _ in range(D)]
sc = sum(C)
M = int(input())
for _ in range(M):
    d, q = map(int, input().split())
    out[d-1] = q - 1
    print(scoring(sc))
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()

ans = 0
if P == 2 or P == 5:
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i+1
else:
	t = [0] * 20000
	t[0] = 1
	now = 0
	for i in range(N):
		n = N - i - 1
		now = (int(S[n]) * pow(10,i) + now) % P
		ans += t[now]
		t[now] += 1
print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()
 
ans = 0
if P == 2 or P == 5:
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i+1
else:
	t = [0] * 20000
	t[0] = 1
	now = 0
	po = 1
	for i in range(N):
		n = N - i - 1
		now = (int(S[n]) * po + now) % P
		po = 10 * po % P
		ans += t[now]
		t[now] += 1
print(ans)
### BUGGY CODE ###

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
Q = int(input())
qs = list(map(int, input().split()))
cs = [0] * (N + 1)
c = []
d = []
for i in range(N):
  cs[i + 1] = cs[i] + (S[i] == "M")
  if S[i] == "C": c.append(i)
  if S[i] == "D": d.append(i)
ccs = [0] * (len(c) + 1)
ls = [0] * N
for i in range(len(c)):
  ccs[i + 1] = ccs[i] + cs[c[i]]
for i in range(N):
  if S[i] == "D": ls[i] = bl(c, i)

#print(c, ccs)
#print(d)
for k in qs:
  res = 0
  for i in d:
    l = ls[i]
    r = bl(c, i + k)
    res += max(0, ccs[r] - ccs[l] - cs[i] * (r - l))
  print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
Q = int(input())
qs = list(map(int, input().split()))
cs = [0] * (N + 1)
c = []
d = []
for i in range(N):
  cs[i + 1] = cs[i] + (S[i] == "M")
  if S[i] == "C": c.append(i)
  if S[i] == "D": d.append(i)
ccs = [0] * (N + 1)
ccounts = [0] * (N + 1)
for i in range(N):
  ccs[i + 1] = ccs[i] + cs[i] * (S[i] == "C")
  ccounts[i + 1] = ccounts[i] + (S[i] == "C")

#print(cs, c)
#print(ccs)
for k in qs:
  res = 0
  for i in d:
    l = i
    r = min(N, i + k)
    res += max(0, ccs[r] - ccs[l] - cs[i] * (ccounts[r] - ccounts[l]))
  print(res)
### BUGGY CODE ###

a,b = map(int,input().split())
c = 0
for i in range(a+1):
    for j in range(a+1):
        for k in range(a+1):
            if i+j+k== b:
                c+=1
print(c)

### FIXED CODE ###

a,b = map(int,input().split())
c = 0
for i in range(a+1):
    for j in range(a+1):
        z = b-i-j
        if i+j+z==b and 0<=z<=a:
            c+=1
print(c)
### BUGGY CODE ###

import heapq

def dijkstra(m, s, t):
    INF = 1e10
    D = [INF] * N
    D[s] = 0
    Q = [(0 if s == v else INF, v) for v in range(N)]
    heapq.heapify(Q)

    while Q:
        c, u = heapq.heappop(Q)
        if D[u] < c:
            continue
        for v, w in enumerate(m[u]):
            if D[v] > D[u] + w:
                D[v] = D[u] + w
                heapq.heappush(Q, (D[u]+w, v))
    return D[t] 

N, M = map(int, input().split())

# N < 100
m = [[1e10]*N for i in range(N)]
E = [0] * M
for i in range(M):
    a, b, w = map(int, input().split())
    E[i] = a-1, b-1, w
    m[a-1][b-1] = w
    m[b-1][a-1] = w

count = 0
for a, b, w in E:
    d = dijkstra(m, a, b)
    #print((a+1, b+1), d, "w=%d"%w)
    if d < w:
        count += 1

print(count)


### FIXED CODE ###

import heapq

def dijkstra(m, s, t):
    INF = 1e10
    D = [INF] * N
    D[s] = 0
    Q = [(0 if s == v else INF, v) for v in range(N)]
    heapq.heapify(Q)

    while Q:
        c, u = heapq.heappop(Q)
        if D[u] < c:
            continue
        for v, w in m[u]:
            if D[v] > D[u] + w:
                D[v] = D[u] + w
                heapq.heappush(Q, (D[u]+w, v))
    return D[t] 

N, M = map(int, input().split())

# N < 100
m = [[] for i in range(N)]
E = [0] * M
for i in range(M):
    a, b, w = map(int, input().split())
    E[i] = a-1, b-1, w
    m[a-1].append((b-1,w))
    m[b-1].append((a-1,w))

count = 0
for a, b, w in E:
    d = dijkstra(m, a, b)
    #print((a+1, b+1), d, "w=%d"%w)
    if d < w:
        count += 1

print(count)
### BUGGY CODE ###

import math

N = int(input())

numbers_full = []
for _ in range(N):
  numbers_full.append(int(input()))

for i in range(N):
  numbers_minus1 = numbers_full.copy()
  numbers_minus1[i] = 0
  print(str(max(numbers_minus1)))

### FIXED CODE ###

N = int(input())
number_list = [int(input()) for _ in range(N)]

sorted_num = sorted(number_list)
number_max = sorted_num[-1]
number_second_max = sorted_num[-2]

if number_max == number_second_max:
  output_always_max = True
else:
  output_always_max = False

for number in number_list:
  if output_always_max:
    print(str(number_max))
  else:
    if number == number_max:
      print(str(number_second_max))
    else:
      print(str(number_max))
### BUGGY CODE ###

import numpy as np

N = int(input())
Ai = list(map(int, input().split()))

ans = ""

Aians = sorted(enumerate(Ai), key = lambda x: x[-1])

for ansNum in Aians:
    ans = ans + str(ansNum[0] + 1) + " "

print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
Ai = list(map(int, input().split()))

#Aians = np.argsort(Ai) + 1
print(' '.join(map(str, np.argsort(Ai) + 1)))