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

list=list(map(int,input().split()))
x=list[0]
k=list[1]
y=abs(x-k)
while y>=k:
  y=abs(y-k)
z=k-y
if z >=y:
  print(y)
else:
  print(z)
  

### FIXED CODE ###

list=list(map(int,input().split()))
x=list[0]
k=list[1]
if list[0]>=list[1]:
  x=x%k
z=abs(k-x)
if z >=x:
  print(x)
else:
  print(z)
### BUGGY CODE ###

X=int(input())
A=[]
for i in range(1,X+1):
    A.append(i)
    if sum(A)>=X:
        print(i)
        break

### FIXED CODE ###

sum=0
X=int(input())
for i in range(1,X+1):
    sum+=i
    if sum>=X:
        print(i)
        break
### BUGGY CODE ###

A, B, K = list(map(int,input().split(' ')))
x = [i for i in range(A,B+1)]
s_f,s_b = x[:K],x[len(x)-K:]
ans = s_f + s_b
ans =list(set(ans))
ans.sort()

[print(i) for i in ans]


### FIXED CODE ###

A, B, K = list(map(int,input().split(' ')))
'''
x = [i for i in range(A,B+1)]
s_f,s_b = x[:K],x[len(x)-K:]
ans = s_f + s_b
ans =list(set(ans))
#ans.sort()
if len(range(A,B+1))<K:
  [print(i) for i in range(A,B+1)]
else:
  x = [i for i in range(A,B+1)]
  s_f,s_b = x[:K],x[len(x)-K:]
  ans = s_f + s_b
  ans =list(set(ans))
  ans.sort()
  [print(i) for i in ans]

'''
if (B-A+1)<K:
  s =  list(range(A,B+1))
  [print(i) for i in s]
else:           
  s_f = list(range(A,A+K))
  s_b = list(range(B,B-K,-1))
  ans = s_f + s_b
  ans =list(set(ans))
  ans.sort()
  [print(i) for i in ans]
### BUGGY CODE ###

import math
k=int(input())
sum=0
    
for i in range(1,k+1):
  for j in range(1,k+1):
    for z in range(1,k+1):
      sum+=math.gcd(i,math.gcd(j,z))
      
print(sum)

### FIXED CODE ###

k=int(input())
sum=0

def gcd(x,y):
  while y!=0:
    x,y=y,x%y
  return x
    
for i in range(1,k+1):
  for j in range(1,k+1):
    for z in range(1,k+1):
      sum+=gcd(i,gcd(j,z))
      
print(sum)
### BUGGY CODE ###

import functools
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])

@functools.lru_cache(None)
def maxvalue(i, w):
    if i < 0: return 0
    if w < ws[i]:
        return maxvalue(i - 1, w)
    else:
        return max(maxvalue(i - 1, w), maxvalue(i - 1, w - ws[i]) + vs[i])

print(maxvalue(N - 1, W))

### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())
ws, vs = zip(*[map(int, input().split()) for _ in range(N)])
INF = 10**13

def maxvalue_dp(ws, vs, W):
    V = sum(vs)
    dp = np.zeros(V + 1, np.int64)
    dp += INF
    dp[0] = 0
    for w, v in zip(ws, vs):
        dp[v:] = np.minimum(dp[v:], dp[:-v] + w)
    for v in range(V, -1, -1):
        if dp[v] <= W:
            return v

print(maxvalue_dp(ws, vs, W))
### BUGGY CODE ###

import copy
def main():
    line = input().split(' ')
    N, M = int(line[0]), int(line[1])
    root = [list(map(int, input().split(' '))) for i in range(M)]
    signpost = [0 for i in range(N+1)]

    mem1 = [1]
    while True:
        mem2 = []
        for node in root:
            if node[0] in mem1:
                if signpost[node[1]] == 0 and node[1] != 1:
                    signpost[node[1]] = node[0]
                    mem2.append(node[1])
            elif node[1] in mem1:
                if signpost[node[0]] == 0 and node[0] != 1:
                    signpost[node[0]] = node[1]
                    mem2.append(node[0])
        if len(mem2) == 0:
            break
        mem1.clear()
        #list(set(mem2))
        mem1 = copy.copy(mem2)

    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print(i)        

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

def main():
    N, M = map(int, input().split(' '))
    edge = [[] for i in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split(' '))
        edge[a].append(b)
        edge[b].append(a)
    signpost = [None] * (N+1)
    signpost[0] = signpost[1] = 0
    q = deque([1])
    dist = [0 for i in range(N+1)]
    while q:
        node = q.popleft()
        for e in edge[node]:
            if signpost[e] is None:
                dist[e] = dist[node] + 1
                signpost[e] = node
                q.append(e)
    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print(i)        

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

def main():
    n = int(input())
    x = [int(xn) for xn in input().split()]
    x_sorted = sorted(x)
    idx_median = (n - 1) // 2
    for xn in x:
        target = [*x_sorted]
        target.remove(xn)
        print(target[idx_median])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    x = [int(xn) for xn in input().split()]
    x_sorted = sorted(x)
    idx_median = n // 2
    median_low = x_sorted[idx_median - 1]
    median_high = x_sorted[idx_median]
    for xn in x:
        print(median_high if xn <= median_low else median_low)


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

n=int(input())
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

ans=[]
for num,cnt in factorization(n):
  for _ in range(cnt):
    ans.append(num)
out=float('inf')
for i in range(2**len(ans)):
  tmp1,tmp2=1,1
  for j in range(len(ans)):
    if i>>j&1:
      tmp1*=ans[j]
    else:
      tmp2*=ans[j]
  out=min(out,tmp1-1+tmp2-1)
print(out)

### FIXED CODE ###

import math
n=int(input())

def make_divisors(n):
  divisors=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      divisors.append(i)
      if i!=n//i:
        divisors.append(n//i)
  divisors.sort()
  return divisors
a=make_divisors(n)
if len(a)%2==1:
  print(2*int(math.sqrt(n))-2)
if len(a)%2==0:
  b=a[len(a)//2-1]
  c=a[len(a)//2]
  print(b+c-2)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

L, R = map(int, input().split())

res = 2020
for i in range(L, R):
    for j in range(i+1, R+1):
        res = min(res, (i*j)%2019)

print(res)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

L, R = map(int, input().split())

res = 2020
if R-L >= 2019:
    print(0)
else:
    for i in range(L, R):
        if res==0: break
        for j in range(i+1, R+1):
            if res==0: break
            
            new_res = (i*j)%2019
            if new_res < res:
                res = new_res
    print(res)
### BUGGY CODE ###

N = int(input())
s = []
for _ in range(N):
    si = sorted(input())
    s.append(si)
ans = 0
for i in range(0, N - 1):
    for j in range(i + 1, N):
        if s[i] == s[j]:
            ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter


N = int(input())
c = Counter()
for _ in range(N):
    si = "".join(sorted(input()))
    c[si] += 1

ans = sum([n*(n - 1) // 2 for n in c.values()])
print(ans)
### BUGGY CODE ###

from collections import deque
n,k = (int(i) for i in input().split())
b = [[int(i)-1 for i in input().split()] for i in range(n-1)]
x,d,ans,c = [[] for i in range(n)],[[] for i in range(n)],n,0
for i,j in b:
	x[i].append(j)
	x[j].append(i)
for i in x: c = max(len(i),c)
if n-c+1<=k: ans = 0
elif k==1: ans = n-2
else:
	for i in range(n):
		q,v = deque(),[1]*n
		v[i] = 0
		for j in x[i]:
			q.append((j,1,j))
			d[i].append(j)
			v[j] = 0
		while q:
			p = q.pop()
			if p[1]<k//2:
				for j in x[p[0]]:
					if v[j]:
						q.append((j,p[1]+1,p[2]))
						d[i].append(p[2])
						v[j] = 0
	if k%2:
		for i,j in b: ans = min(ans,n-len(d[i])-len(d[j])+d[i].count(j)+d[j].count(i)-2)
	else:
		for i in range(n): ans = min(ans,n-len(d[i])-1)
print(ans)

### FIXED CODE ###

from collections import deque
n,k = (int(i) for i in input().split())
b = [[int(i)-1 for i in input().split()] for i in range(n-1)]
x,d,ans,c = [[] for i in range(n)],[[] for i in range(n)],n,0
for i,j in b:
	x[i].append(j)
	x[j].append(i)
def f(s):
	for i in range(n):
		q,v = deque(),[1]*n
		v[i] = 0
		for j in x[i]:
			q.append((j,1,j))
			d[i].append(j)
			v[j] = 0
		while q:
			p = q.pop()
			if p[1]<s:
				for j in x[p[0]]:
					if v[j]:
						q.append((j,p[1]+1,p[2]))
						d[i].append(p[2])
						v[j] = 0
if k>n//2:
	for i in x: c = max(len(i),c)
if n-c+1<=k: ans = 0
elif k==1: ans = n-2
else:
	f(k//2)
	if k%2:
		for i,j in b: ans = min(ans,n-len(d[i])-len(d[j])+d[i].count(j)+d[j].count(i)-2)
	else:
		for i in range(n): ans = min(ans,n-len(d[i])-1)
print(ans)
### BUGGY CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

from fractions import gcd
from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)


### FIXED CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
x.sort(reverse=True)
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
items = list(map(int, input().split()))
for _ in range(M):
	items[items.index(max(items))] //= 2
print(sum(items))


### FIXED CODE ###

import heapq
N, M = map(int, input().split())
items = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(items)
for _ in range(M):
	tmp = heapq.heappop(items)
	heapq.heappush(items, int(tmp/2))
print(-sum(items))
### BUGGY CODE ###

N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


for i, x in enumerate(X):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if (x_num - (2**(N-(i+1)))) != 0:
            print(f((x_num - (2 ** (N - (i + 1)))) % (cnt1 - 1)) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        if (x_num + (2**(N-(i+1)))) != 0:
            print(f((x_num + (2 ** (N - (i + 1)))) % (cnt1 + 1)) + 1)
        else:
            print(0)


### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = (x_num % (cnt1 - 1) if cnt1 - 1 > 0 else 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0 else 0
            print(f1(xxx) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        xxx = (p_zero + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0 else 0
        print(f1(xxx) + 1)
### BUGGY CODE ###

N, M = map(int, input().split())
L = []
for i in range(N):
    l, r = map(int, input().split())
    L.append((r-l+1, l, r+1))
L.sort()


class Bit:
    """
    0-indexed
    # 使用例
    bit = Bit(10)  # 要素数
    bit.add(2, 10)
    print(bit.sum(5))  # 10
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)


imos = BitImos(M+1)
il = 0
a = N
A = [0]*M
for i in range(1, M+1):
    while il<N:
        ra, l, r = L[il]
        if i < ra:
            break
        il+=1
        a-=1
        imos.add(l, r, 1)
    ans = 0
    for j in range(i, M+1, i):
        ans += imos[j]

    A[i-1] = ans + a

print(*A, sep="\n")


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N, M = map(int, input().split())
L = []
for i in range(N):
    l, r = map(int, input().split())
    L.append((r-l+1, l, r+1))
L.sort()


class Bit:
    """
    0-indexed
    # 使用例
    bit = Bit(10)  # 要素数
    bit.add(2, 10)
    print(bit.sum(5))  # 10
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)


imos = BitImos(M+1)
il = 0
a = N
A = [0]*M
for i in range(1, M+1):
    while il<N:
        ra, l, r = L[il]
        if i < ra:
            break
        il+=1
        a-=1
        imos.add(l, r, 1)
    ans = 0
    for j in range(i, M+1, i):
        ans += imos[j]

    A[i-1] = ans + a

print(*A, sep="\n")
### BUGGY CODE ###

a, b, q = list(map(int, input().split()))
s = [int(input()) for _ in range(a)]
t = [int(input()) for _ in range(b)]
x = [int(input()) for _ in range(q)]

s.sort()
t.sort()

def bs(z, st):
    l = 0
    r = len(st) - 1
    while r - l != 1:
        m = (l + r) // 2
        if st[m] == z:
            return m
        elif st[m] < z:
            l = m
        else:
            r = m
    return l

for xi in x:
    tmps = []
    tmpt = []
    if xi <= s[0]:
        tmps.append(s[0] - xi)
    elif s[-1] <= xi:
        tmps.append(s[-1] - xi)
    else:
        tmp = bs(xi, s)
        tmps.append(s[tmp] - xi)
        tmps.append(s[tmp + 1] - xi)

    if xi <= t[0]:
        tmpt.append(t[0] - xi)
    elif t[-1] <= xi:
        tmpt.append(t[-1] - xi)
    else:
        tmp = bs(xi, t)
        tmpt.append(t[tmp] - xi)
        tmpt.append(t[tmp + 1] - xi)
    anss = []
    for i in tmps:
        for j in tmpt:
            if i // abs(i) == j // abs(j):
                anss.append(max(abs(i), abs(j)))
            else:
                maxij = max(abs(i), abs(j)) 
                minij = min(abs(i), abs(j)) 
                anss.append(abs(maxij + minij * 2))
    anss.sort()
    print(anss[0])

### FIXED CODE ###

a, b, q = list(map(int, input().split()))
s = [int(input()) for _ in range(a)]
t = [int(input()) for _ in range(b)]
x = [int(input()) for _ in range(q)]

def bs(z, st):
    l = 0
    r = len(st) - 1
    while r - l != 1:
        m = (l + r) // 2
        if st[m] <= z:
            l = m
        else:
            r = m
    return l

for xi in x:
    tmps = []
    tmpt = []
    if xi <= s[0]:
        tmps.append(s[0] - xi)
    elif s[-1] <= xi:
        tmps.append(s[-1] - xi)
    else:
        tmp = bs(xi, s)
        tmps.append(s[tmp] - xi)
        tmps.append(s[tmp + 1] - xi)

    if xi <= t[0]:
        tmpt.append(t[0] - xi)
    elif t[-1] <= xi:
        tmpt.append(t[-1] - xi)
    else:
        tmp = bs(xi, t)
        tmpt.append(t[tmp] - xi)
        tmpt.append(t[tmp + 1] - xi)
    anss = []
    for i in tmps:
        for j in tmpt:
            if i // abs(i) == j // abs(j):
                anss.append(max(abs(i), abs(j)))
            else:
                maxij = max(abs(i), abs(j)) 
                minij = min(abs(i), abs(j)) 
                anss.append(abs(maxij + minij * 2))
    anss.sort()
    print(anss[0])
### BUGGY CODE ###

import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :float("inf"))
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					#self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [float('inf') for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append([q-1 + t * n, 0])
	edges[q-1 + t * n].append([p-1 + t * n, 0])
	edges[p-1 + t * n].append([p-1 + 0 * n, 0])
	edges[q-1 + t * n].append([q-1 + 0 * n, 0])
	edges[p-1 + 0 * n].append([p-1 + t * n, 1])
	edges[q-1 + 0 * n].append([q-1 + t * n, 1])

#print(edges.items())
d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res == float("inf"):
	print(-1)
else:
	print(res)

### FIXED CODE ###

import sys, heapq
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		#self.dist = [float("inf") for _ in range(self.size)]
		self.dist = defaultdict(lambda :10**30)
		self.dist[self.start] = 0
		#self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					#self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
cost = [10**30 for _ in range(n)]
edges = defaultdict(list)
for _ in range(m):
	p, q, t = map(int, input().split())
	edges[p-1 + t * n].append((q-1 + t * n, 0))
	edges[q-1 + t * n].append((p-1 + t * n, 0))
	if len(edges[p-1 + t * n]) == 1:
		edges[p-1 + t * n].append((p-1 + 0 * n, 0))
		edges[p-1 + 0 * n].append((p-1 + t * n, 1))
	if len(edges[q-1 + t * n]) == 1:
		edges[q-1 + t * n].append((q-1 + 0 * n, 0))
		edges[q-1 + 0 * n].append((q-1 + t * n, 1))

d = DijkstraList(edges, 0)
d.solve()
res = d.distance(n-1)
if res > 10**20:
	print(-1)
else:
	print(res)
### BUGGY CODE ###

n, m = map(int, input().split())
if m%n==0:
    print(m//n)
else:
    index=m//n
    while index >0:
        if m%index==0:
            print(index)
            break
        index-=1

### FIXED CODE ###

import math
import time
n, m = map(int, input().split())
flag=0
if m%n==0:
    print(m//n)

else:
    start = time.time()
    index=m//n
    while index >0:
        elapsedTime = time.time()-start
        if elapsedTime > 1:
            flag=1
            break
        elif m%index==0:
            print(index)
            break
        index-=1

    if flag==1:
        index = 1
        while index < m+1:
            if m % index == 0:
                if index > n-1:
                    print(m//index)
                    break
            index += 1
### BUGGY CODE ###

n,m = map(int,input().split())
ls = [int(input()) for _ in range(m)]
dp = [0]*(n+1)
dp[0]=1
if 1 in ls:
    dp[1]= 0
else:
    dp[1]= 1
for i in range(2,n+1):
    if i in ls :
        continue
    else:
        dp[i] = dp[i-1]+dp[i-2]
print(dp[n]%(10**9+7))

### FIXED CODE ###

n,m = map(int,input().split())
ls = set()
for i in range(m):
    ls.add(int(input()))
dp = [0]*(n+1)
dp[0]=1
if 1 in ls:
    dp[1]= 0
else:
    dp[1]= 1
for i in range(2,n+1):
    if i in ls :
        continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[n]%(10**9+7))
### BUGGY CODE ###

N, W = map(int, input().split())
Wl, Vl = [], []
for i in range(N):
    w, v = map(int, input().split())
    Wl.append(w); Vl.append(v)

dp = [[10**9+1]*(10**7) for _ in range(N+2)]
dp[0][0] = 0

ans = 0
for i in range(N):
    w, v = Wl[i], Vl[i]
    for j in range(10**5):
        if j+v < 10**9+1:
            dp[i+1][j+v] = min(dp[i+1][j+v],
                                dp[i][j]+w)
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if dp[i+1][j+v] <= W: ans=max(ans, j+v)
        if dp[i+1][j] <= W: ans=max(ans, j)
print(ans)

### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())
dp = np.full(N*10**3+1, W+1)
dp[0] = 0

for i in range(N):
    w, v = map(int, input().split())
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
print(np.where(dp<=W)[0][-1])