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

import bisect

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

for m in range(M):
  x = A.pop() // 2
  A.insert(bisect.bisect_left(A, x),x)
print(sum(A))



### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda x:[-int(x),int(x)], input().split()))
heapq.heapify(A)

for m in range(M):
  x = heapq.heappop(A)
  x[1] //= 2
  x[0] = -x[1]
  heapq.heappush(A, x)
ans = 0
for a in A:
  ans += a[1]
print(ans)
### BUGGY CODE ###

import math
K = int(input())
ans = 0

def gcd3(a, b, c):
    lst = [a, b, c]
    slst = sorted(lst)
    t = math.gcd(slst[0], slst[1])
    s = math.gcd(t, slst[2])
    return s

for i in range(1, K +1):
    for j in range(1, K+1):
        for t in range(1, K+1):
            ans += gcd3(i, j, t)

print(ans)

### FIXED CODE ###

import math
k = int(input())
ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        gcd1 = math.gcd(i,j)
        for t in range(1, k+1):
            ans += math.gcd(gcd1, t)

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

import sys
#input = sys.stdin.buffer.readline

def main():
    N = int(input())
    S = str(input())

    def z_algo(S):
        N = len(S)
        A = [0]*N
        i = 1; j = 0
        A[0] = l = len(S)
        while i < l:
            while i+j < l and S[j] == S[i+j]:
                j += 1
            if not j:
                i += 1
                continue
            A[i] = j
            k = 1
            while l-i > k < j - A[k]:
                A[i+k] = A[k]
                k += 1
            i += k; j -= k
        return A
        
    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        ans = max(ans,max(z[-((N-i)//2):]))
        
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline

def main():
    N = int(input())
    s = input()
    a,i,j = 0,0,1
    
    while j < N:
        if s[i:j] in s[j:]:
            a = max(a,j-i)
            j += 1
        else:
            i += 1
        if i == j:
            i += 1
            j += 2
            
    print(a)

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

from math import gcd
from bisect import insort

N = int(input())
A = list(map(int, input().split()))
mA = max(A)
primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    #return None
    return False

primecounter = [0 for _ in range(len(primenum))]
biggerprime = []
def factorization(n):
  M = n
  for k in range(len(primenum)):
    p = primenum[k]
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if primecounter[k] == 0:
          primecounter[k] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if binary_search(biggerprime, M):
      return False
    else:
      insort(biggerprime, M)
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)
  if flag == False:
    if g == 1:
      break


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')


### FIXED CODE ###

from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

import queue
h,w=map(int,input().split())
a=[input() for _ in range(h)]
q=[]
dist=[[-1 for _ in range(w)]for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append([i,j])
            dist[i][j]=0
q=queue.deque(q)
d=[[1,0],[0,1],[-1,0],[0,-1]]
while q:
    y,x=q.popleft()
    for dy,dx in d:
        ny,nx=y+dy,x+dx
        if 0<=ny and ny<h and 0<=nx and nx<w and dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            q.append([ny,nx])
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,dist[i][j])
print(ans)

### FIXED CODE ###

import queue
h,w=map(int,input().split())
a=[input() for _ in range(h)]
q=[]
dist=[[-1 for _ in range(w)]for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append([i,j])
            dist[i][j]=0
q=queue.deque(q)
d=[[1,0],[0,1],[-1,0],[0,-1]]
while q:
    y,x=q.popleft()
    for dy,dx in d:
        ny,nx=y+dy,x+dx
        if 0<=ny and ny<h and 0<=nx and nx<w and dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            q.append([ny,nx])
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,dist[i][j])
print(ans)
### BUGGY CODE ###

def examE():
    N, T = LI()
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = LI()
    dp = [[[0,0] for _ in range(T+ 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(A[i],T+1):
            dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j - A[i]][0] + B[i])
            dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j - A[i]][1] + B[i])
        for j in range(1,T+1):
            dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j-1][0] + B[i])
            dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][0])
            dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j][1])
#    print(dp[N][T])
    ans = max(dp[N][T])
    print(ans)

import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE()


### FIXED CODE ###

def examE():
    N, T = LI()
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = LI()
    dp = [[0 for _ in range(T+ 1)] for _ in range(N + 1)]
    dp2 = [[0 for _ in range(T+ 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(A[i],T+1):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - A[i]] + B[i])
            dp2[i + 1][j] = max(dp2[i + 1][j], dp2[i][j - A[i]] + B[i])
        for j in range(1,T+1):
            dp2[i+1][j] = max(dp2[i+1][j], dp[i][j-1] + B[i], dp2[i][j])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
#    print(dp[N][T])
    ans = dp2[N][T]
    print(ans)

import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE()
### BUGGY CODE ###

N, *a = map(int, open(0).read().split())

ans = 1
for x in a:
    ans = ans * x
    if ans == 0:
      print(0)
      exit()

if 10 ** 18 < ans:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N, *a = map(int, open(0).read().split())

if 0 in a:
    print(0)
    exit()

ans = 1
for x in a:
    ans = ans * x
    if 10 ** 18 < ans:
        print(-1)
        exit()

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

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

if k==0:
    print(n**2)
    quit()

cnt=0
for a in range(k,n+1):
    for b in range(k,n+1):
        if a<k or b<k:
            continue
        if a%b >= k:
            cnt+=1

print(cnt)


### FIXED CODE ###

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

s = 0
for b in range(1, n+1):
    s += max(0, b-k)*(n//b) + max(0, n%b-k+1)

if k == 0:
    s = n*n
print(s)
### BUGGY CODE ###

def nPr(n, r):
  ans = 1
  for i in range(n,n-r,-1):
    ans *= i
  return ans

def nCr(n, r):
  tmp = 1
  for i in range(r,1,-1):
    tmp *= i
  return int(nPr(n, r) / tmp)

n = int(input())
a = list(map(int,input().split()))
count = len(a)
d = {}

for i in a:
  if i not in d:
    d[i] = 1
  else:
    d[i] += 1
#print(d)

for i in a:
  ans = 0
  for j in d:
    if i == j:
      if d[j] > 2:
        ans += nCr(d[j]-1, 2)
    else:
      if d[j] > 1:
        ans += nCr(d[j], 2)
  print(ans)
      

### FIXED CODE ###

def nPr(n, r):
  ans = 1
  for i in range(n,n-r,-1):
    ans *= i
  return ans

def nCr(n, r):
  tmp = 1
  for i in range(r,1,-1):
    tmp *= i
  return int(nPr(n, r) / tmp)

n = int(input())
a = list(map(int,input().split()))
count = len(a)
d = {}
x = 0

for i in a:
  if i not in d:
    d[i] = 1
  else:
    d[i] += 1

for i in d:
  x += nCr(d[i], 2)

for i in a:
  ans = x - d[i] + 1
  print(ans)
### BUGGY CODE ###

import math
a, b, n = map(int, input().split())

n = min(n, b)


mem = {}
m = 0
for x in range(1, n + 1):
    if mem.get(((a * x) % b, x % b)) is not None:
        break    
    else:
        c = math.floor(a * x / b) - a * math.floor(x / b)
        mem[((a * x) % b, x % b)] = 1
        m = max(m, c)
print(m)


### FIXED CODE ###

import math
a, b, n = map(int, input().split())

n = min(n, b-1)

print(math.floor(a * n / b) - a * math.floor(n / b))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
MOD=10**9+7
def dfs(v,p):
    if seen[v]:
        return dp[v]
    seen[v]=1
    b,w=1,1
    for nv in G[v]:
        if(nv==p):
            continue
        bw=dfs(nv,v)
        w*=sum(bw);w%=MOD
        b*=bw[1];b%=MOD
    dp[v]=(b,w)
    return (b,w)
    
N=int(input())
G,dp,seen=[],[],[]
for i in range(N):
    G.append([]);dp.append([0,0]);seen.append(0)
for i in range(N-1):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
    G[y].append(x)
print(sum(dfs(0,-1))%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
MOD=10**9+7
def dfs(v,p):
    if seen[v]:
        return dp[v]
    seen[v]=1
    b,w=1,1
    for nv in G[v]:
        if(nv==p):
            continue
        bw=dfs(nv,v)
        w*=sum(bw);w%=MOD
        b*=bw[1];b%=MOD
    dp[v]=(b,w)
    return (b,w)
    
N=int(input())
G,dp,seen=[],[],[]
for i in range(N):
    G.append([]);dp.append([0,0]);seen.append(0)
for i in range(N-1):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
    G[y].append(x)
print(sum(dfs(0,-1))%MOD)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = []
    for i in range(1, len(A)+1):
        ans.append(A.index(i)+1)
    print(*ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    tmp = []
    for i, a in enumerate(A):
        tmp.append((i, a))
    tmp.sort(key=lambda a: a[1])
    ans = []
    for i in tmp:
        ans.append(i[0]+1)
    print(*ans)

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

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

# 数値Aの頻度
ndic = {}
for i in A:
    if i in ndic:
        ndic[i] += 1
    else:
        ndic[i] = 1

# 2つの同じ数値Aの選び方
cdic = {}
mem = {}
for j in ndic:
    if ndic[j] == 1:
        continue
    
    if ndic[j] in mem:
        cdic[j] = mem[ndic[j]]
    else:
        cdic[j] = int((ndic[j] * (ndic[j] -1)) / 2)
        mem[ndic[j]] = cdic[j]

buff = ""
for i in A:
    cmb = 0
    for j in cdic:
        if i == j and cdic[j] > 0:
            cmb += cdic[j] - (ndic[j] - 1)
        else:
            cmb += cdic[j]
    buff += str(cmb) + "\n"

print(buff)

### FIXED CODE ###

import collections

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

# 数値Aの頻度
ndic = collections.Counter(A)

mem = {}
tcmb = 0
for j in ndic:
    if ndic[j] == 1:
        continue
    
    if ndic[j] in mem:
        tcmb += mem[ndic[j]]
    else:
        mem[ndic[j]] = int((ndic[j] * (ndic[j] -1)) / 2)
        tcmb += mem[ndic[j]]
        
for i in A:
    cmb  = tcmb - (ndic[i] - 1)
    print(cmb)
### BUGGY CODE ###

k, s = map(int, input().split())
print(sum([1 for i in range(k+1) for j in range(k+1) for l in range(k+1) if i + j + l == s]))

### FIXED CODE ###

k, s = map(int, input().split())
print(sum([1 for i in range(k+1) for j in range(k+1) if i + j <= s <= i + j + k]))
### BUGGY CODE ###

import math

def main(): 

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

    for i in range(n):
        t = list(a)
        t.pop(i)

        print(max(t))




if __name__ == "__main__":
    main() 

### FIXED CODE ###


def main(): 

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

    max_v = 0
    max_sv = 0

    for i in range(n):
        if a[i] > max_v:
            max_sv = max_v
            max_v = a[i]
        elif a[i] > max_sv:
            max_sv = a[i]

    for i in range(n):
        if a[i] != max_v:
            print(max_v)
        else:
            print(max_sv)




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

def main():
    S = list(input())
    dp = [[0] * 13 for _ in range(10 ** 5 + 1)]
    dp[0][0] = 1
    n = len(S)
    for i in range(n):
        c = 0
        if S[i] == '?':
            c = -1
        else:
            c = int(S[i])
        for si in range(10):
            if c != -1 and c != si:
                continue
            for j in range(13):
                dp[i + 1][(j * 10 + si) % 13] += dp[i][j]
        for j in range(13):
            dp[i + 1][j] %= 10 ** 9 + 7
    print(dp[n][5])


main()


### FIXED CODE ###

def main():
    S = list(input())
    dp = [[0] * 13 for _ in range(10 ** 5 + 1)]
    dp[0][0] = 1
    n = len(S)
    for i in range(n):
        c = 0
        if S[i] == '?':
            c = -1
        else:
            c = int(S[i])
        for si in range(10):
            if c != -1 and c != si:
                continue
            for j in range(13):
                dp[i + 1][(j * 10 + si) % 13] += dp[i][j]
        for j in range(13):
            dp[i + 1][j] %= 10 ** 9 + 7
    print(dp[n][5])


main()
### BUGGY CODE ###

# もらうdpでとく
N, K = map(int, input().split())  # N個のマス, K個の集合
move = []
for _ in range(K):
    l, r = map(int, input().split())
    for d in range(l, r+1):
        move.append(d)
move.sort()

MOD = 998244353
dp = [0]*(N)  # スタート地点0~ゴール地点N-1までのN個
dp[0] = 1
for i in range(N):
    for d in move:
        if i-d < 0:  # 遷移元がないならcontinue
            continue
        dp[i] += dp[i-d]
        dp[i] %= MOD
print(dp[N-1])


### FIXED CODE ###

"Binary Indexed Tree"
"""
- iが与えられたときa1~aiまでの和を計算する O(log n)
- iとxが与えられたときai += x とする O(log n)
"""
# BIT: Binary Indexed Tree (1-indexed), 0-indexだと困るので。
# A1~Aiまでの和 O(logN)


def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)  # 次に求める区間のindexは今見ているindexから今見ている区間の長さ(これはidx&(-idx)で求めることができる)を引くことでindexを求めることができる
    return res_sum


# Ai += x  O(logN)
def BIT_updata(idx, x):
    while idx <= N:
        BIT[idx] += x
        idx += (idx&(-idx))  # 次に更新すべき区間のindexは今見ているindexに今見ている区間の長さを足すことでindexを求めることができる
    return


# n = 8
# BIT = [0]*(n+1)  # 最初に0で初期化する
# a = [1, 2, 3, 4, 5, 6, 7, 8]
# for i, e in enumerate(a):
#     BIT_updata(i+1, e)
#
#
# # A0~A2の和: 6
# print(BIT_query(3))  # ここのアクセスは1-indexで考えている
# # A3~A6の和: 18
# print(BIT_query(6)-BIT_query(2))  # ここのアクセスは1-indexで考えている
# print(BIT)

# BIT_queryで10~15マス前の和を現在のところに加える
N, K = map(int, input().split())
move = []
for _ in range(K):
    l, r = map(int, input().split())
    move.append([l, r])
MOD = 998244353
BIT = [0]*(N+1)  # スタート地点1~ゴール地点NまでのN個 (1-indexed)
BIT_updata(1, 1)
for i in range(2, N+1):
    for l, r in move:
        # lマス前からrマス前までの区間和を現在のマスに加える
        BIT_updata(i, (BIT_query(i-l)-BIT_query(i-r-1))%MOD)
ans = BIT_query(N) - BIT_query(N-1)
print(ans%MOD)
# BIT_query(N-10) - BIT_query(N-15)を現在のところにタス
# いや，微妙に違う?
### BUGGY CODE ###

S = list(input())
N = len(S)
b = True
ans = 0
while b:
    b = False
    for i in range(N-2):
        if S[i] == 'A' and S[i+1] == 'B' and S[i+2] == 'C':
            b = True
            S[i] = 'B'
            S[i+1] = 'C'
            S[i+2] = 'A'
            ans += 1
print(ans)


### FIXED CODE ###

S = list(input())
N = len(S)

if S[0] == 'A':
    ac = 1
else:
    ac = 0

ans = 0
for i in range(1,N):
    if S[i] == 'A':
        if S[i-1] != 'A':
            ac = 1
        else:
            ac += 1
    elif S[i] == 'B':
        if S[i-1] != 'A':
            ac = 0
    else:
        if S[i-1] == 'B':
            ans += ac
            S[i] = 'A'
        else:
            ac = 0

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

def main():
    import itertools,copy,sys
    input = sys.stdin.readline
    T = list(input())
    TC = T
    N = [i for i, x in enumerate(T) if x == '?']
    B = list(itertools.product(['P','D'], repeat=len(N)))
    point = [0]*len(B)
    strs = ['']*len(B)
    for b,i in zip(B,range(len(B))):
        TC = copy.deepcopy(T)
        TC_count = TC.count
        for n,j in zip(N,range(len(N))):
            TC[n] = b[j]
        TC = ''.join(TC)
        strs[i] = TC
        point[i] = TC_count('PD') + TC_count('D')
    maxin = max(point)

    print(strs[point.index(maxin)])
main()

if __name__ == '__main__':
    main()

### FIXED CODE ###

#BBBBBBBBBBB

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

t = rl()
li = []
for i in range(len(t)):
    if t[i] == '?':
        li.append('D')
    else:
        li.append(t[i])
print(''.join(li))
### BUGGY CODE ###

n = int(input())
s = input()
sum=0

for i in range(n):
    for j in range(n):
        for k in range(n):
            if not (i<j<k):
                continue
            if (s[i]!=s[j])&(s[j]!=s[k])&(s[k]!=s[i])&(j-i!=k-j):
                sum+=1

print(sum)


### FIXED CODE ###

n=int(input())
s=input()
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=r*g*b

for i in range(n):
    for d in range(n):
        j=i+d
        k=j+d
        if k>=n:
            break
        if (s[i]!=s[j]) & (s[j]!=s[k]) & (s[k]!=s[i]):
            ans-=1

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

import sys
from collections import deque


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    costs = [10 ** 9] * n
    corporations = [set() for _ in range(n)]
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if costs[v] < d:
            continue
        elif costs[v] == d:
            if e in corporations[v]:
                continue
        else:
            costs[v] = d
        corporations[v].add(e)
        for u, c in links[v]:
            if c == e:
                nd = d
                func = q.appendleft
            else:
                nd = d + 1
                func = q.append
            if costs[u] < nd or c in corporations[u]:
                continue
            func((nd, u, c))
    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [set() for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p].add((q, c))
    links[q].add((p, c))

print(bfs01(0, n - 1, links))


### FIXED CODE ###

import sys
from collections import deque, defaultdict


def bfs01(s, t, links):
    q = deque([(0, s, -1)])  # cost, station, last-company
    visited = set()
    while q:
        d, v, e = q.popleft()
        if v == t:
            return d
        if (v, e) in visited:
            continue
        visited.add((v, e))
        if e == 0:
            for c in links[v]:
                for u in links[v][c]:
                    if (u, c) in visited:
                        continue
                    q.append((d + 1, u, c))
        else:
            for u in links[v][e]:
                if (u, e) in visited:
                    continue
                q.appendleft((d, u, e))
            if (v, 0) not in visited:
                q.appendleft((d, v, 0))

    return -1


readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

n, m = map(int, readline().split())
links = [defaultdict(set) for _ in range(n)]
pqc = list(map(int, read().split()))
for p, q, c in zip(pqc[0::3], pqc[1::3], pqc[2::3]):
    p -= 1
    q -= 1
    links[p][c].add(q)
    links[q][c].add(p)

print(bfs01(0, n - 1, links))
### BUGGY CODE ###

[n,k]=list(map(int,input().split()))
akarusa=list(map(int,input().split()))


for i in range(k):
    akarusanext=[0]*n
    imos=[0]*n
    for j in range(n):
        kagen=max(j-akarusa[j],0)
        jogen=min(j+akarusa[j],n-1)
        imos[kagen]+=1
        if jogen+1<n:
            imos[jogen+1]-=1
    akarusanext=[imos[0]]
    for j in range(1,n):
        akarusanext.append(akarusanext[-1]+imos[j])
    
    akarusa=akarusanext
    if min(akarusa)==n:
        break

for i in range(n):
    print(akarusa[i], end=" ")


### FIXED CODE ###

[n,k]=list(map(int,input().split()))
akarusa=list(map(int,input().split()))


for i in range(k):
    imos=[0]*n
    for j in range(n):
        kagen=max(j-akarusa[j],0)
        jogen=min(j+akarusa[j],n-1)
        imos[kagen]+=1
        if jogen+1<n:
            imos[jogen+1]-=1
    akarusanext=imos
    for j in range(1,n):
        akarusanext[j]+=akarusanext[j-1]
    
    if akarusa==akarusanext:
        break
    else:
        akarusa=akarusanext

for i in range(n):
    print(akarusa[i], end=" ")
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
S = []
for i in range(1,N+1):
    for j in range(N):
        if i == A[j]:
            S.append(j+1)
print(*S)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=[]
kari=[]
for i in range(N):
    ans.append([A[i],i+1])
ans.sort()
#print(ans)
for j in range(N):
    kari.append(ans[j][1])
print(*kari)
### BUGGY CODE ###

def main():
    N, Y = [int(i) for i in input().split()]

    A = []
    B = []

    for i in range(N):
        a, b = [int(i) for i in input().split()]
        A.append(a)
        B.append(b)

    B.sort()
    B.reverse()
    A.sort()
    A.reverse()

    for i in range(1000000000):
        if Y <= 0:
            print(i)
            return

        b_m = max(B, default=0)
        a_m = max(A)
        if b_m > a_m:
            Y = Y - b_m
            B.remove(b_m)
        else:
            Y = Y - a_m


main()


### FIXED CODE ###

def answer():
    import sys
    input = sys.stdin.readline
    wield = 0
    l = []
    N, H = map(int, input().split())
    for i in range(N):
        a, b = map(int, input().split())
        l.append(b)
        wield = max(a, wield)
    l.sort(reverse=True)
    ret = 0
    for a in l:
        if H <= 0:
            break
        if a > wield:
            ret += 1
            H -= a
        else:
            break
    if H > 0:
        ret += (H + wield - 1) // wield
    print(ret)
  
answer()
### BUGGY CODE ###

n, k, q = map(int, input().split())
point = [k] * n
for i in range(q) :
    a = int(input())
    for j in range(n) :
        if j != a - 1 :
            point[j] -= 1
for _ in range(n) :
    if point[_] <= 0 :
        print("No")
    else :
        print("Yes")


### FIXED CODE ###

n, k, q = map(int, input().split())
a = list(int(input()) for i in range(q))
add = [0] * n
def func(x) :
    return k-q+x
for i in range(q) :
    add[a[i]-1] += 1
point = list(map(func, add))
for _ in range(n) :
    if point[_] <= 0 :
        print("No")
    else :
        print("Yes")