Harryxun/stf_run huggingface dataset:
from math import gcd
inpl = lambda: list(map(int,input().split()))
def primes(N):
    P = []
    for i in range(2,N):
        sieve = 1
        for p in P:
            if p*p > i:
                break
            elif i % p == 0:
                sieve = 0
                break
        if sieve == 0:
            continue
        else:
            P.append(i)
    return P

N = int(input())
A = inpl()

g = A[0]
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

P = primes(1000)
for p in P:
    n = 0
    for i in range(N):
        if A[i] % p == 0:
            n += 1
            while A[i] % p == 0:
                A[i] //= p
            if n > 1:
                print('setwise coprime')
                exit()
s = set()
for a in A:
    if a == 1:
        continue
    elif a in s:
        print('setwise coprime')
	    exit()
    else:
        s.add(a)
print('pairwise coprime')


### FIXED CODE ###

from math import gcd
inpl = lambda: list(map(int,input().split()))
def primes(N):
    P = []
    firstfactor = [1]*N
    for i in range(2,N):
        sieve = 1
        for p in P:
            if p*p > i:
                break
            elif i % p == 0:
                sieve = 0
                firstfactor[i] = p
                break
        if sieve == 0:
            continue
        else:
            firstfactor[i] = i
            P.append(i)
    return P, firstfactor

N = int(input())
A = inpl()

g = A[0]
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

ff = primes(max(A)+1)[1]
st = set()
for a in A:
    prev = 0
    while a > 1:
        p = ff[a]
        a //= p
        if p == prev:
            continue
        elif p in st:
            print('setwise coprime')
            exit()
        else:
            prev = p
            st.add(p)
print('pairwise coprime')
N=int(input())
for n in range(1,N+1):
    s=0
    for x in range(1,101):
        for y in range(x,101):
            for z in range(y,101):
                fn=x*x+y*y+z*z+x*y+y*z+z*x
                if fn==n and x==y and x==z:
                    s=s+1
                if fn==n and x<y and y==z:
                    s=s+3
                if fn==n and x==y and y<z:
                    s=s+3              
                if fn==n and x<y and y<z:
                    s=s+6    
    print(n,s)   

### FIXED CODE ###

l, r, D = input().split()
L=int(l)
R=int(r)
d=int(D)
s=0
for i in range(L,R+1):
    if i%d==0:
        s=s+1
print(s)
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
    
N = int(input())
 
a = int(input())
b = 0
for i in range(N-1):
    b = int(input())
    a = (a*b) // gcd(a,b)
    
print(a)

### FIXED CODE ###

a = input()
b = []

for i in range(len(a)):
    b.insert(0, a[i])
    
if list(a) == b:
    print("Yes")
else:
    print("No")
n,m=map(int,input().split())
a=0
a+=map(int,input().split())
if(n>a):
  print("{}",n-a)
else:
  print("-1",

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
p=0
for i in a:
      p+=i
if(n>=p):
          print("{}".format(n-p))
else:
          print("-1")
N,M=map(int,input().split())
L=[]

ans=0

for i in range(N):
    a,b=map(int,input().split())

    L.append([a,b])

L= sorted(L)



for i in range(N):

    if M < L[i][1]
        ans=L[i][0]*M

        print(ans)
        exit()
        
    else:


        ans = L[i][0]*L[i][1]
        M -= L[i][1]


            if M==0:

                print(ans)
                exit()


            if M <= L[i+1][1]:

                ans += M * L[i+1][0]

                print(ans)

                exit()

        




### FIXED CODE ###

N,M=map(int,input().split())
L=[]
ans=0

for i in range(N):
    a,b=map(int,input().split())

    L.append([a,b])

L= sorted(L)

for i in range(N):

    if M < L[i][1]:
        ans=L[i][0]*M

        print(ans)
        exit()
        
    else:
        ans += L[i][0]*L[i][1]
        M -= L[i][1]

        if M==0:

            print(ans)
            exit()

        elif M <= L[i+1][1]:

            ans += M * L[i+1][0]
            print(ans)
            exit()
import math

a,b = map(str,input().split())

c = a + b

if(math.sqrt(c) == int(math.sqrt(c))):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import math
 
a,b = map(str,input().split())
 
c = int(a + b)
 
if(math.sqrt(c) == int(math.sqrt(c))):
  print('Yes')
else:
  print('No')
n, k = map(int, input().split())

a = 1
for i in range(k, n + 1):
  mmin = summ(i - 1)
  mmax = summ(n, n - i)
  m = mmax - mmin + 1
  a += m
  # print('{},{},{}'.format(i, mmin, mmax))

  k = 10**9 + 7
  print(a%k)

    
def summ(n, nn=0):
  nn = max(nn, 0)
  return n*(n+1)/2 - nn*(nn+1)/2


### FIXED CODE ###

def summ(n, nn=0):
  nn = max(nn, 0)
  return n*(n+1)/2 - nn*(nn+1)/2

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

a = 1
for i in range(k, n + 1):
  mmin = summ(i - 1)
  mmax = summ(n, n - i)
  m = mmax - mmin + 1
  a += m

k = 10**9 + 7
print(int(a%k))
a,b.c=map(int,input().split())
L=list[a,b,c]
L.sort()
if L[0]==L[2]:
  print(1)
elif　L[0]<L[1]<L[2]:
  print(3)
else:
  print(2)

### FIXED CODE ###

a,b,c=map(int,input().split())
if a==b==c:
  print(1)
elif a==b or b==c or c==a:
  print(2)
else:
  print(3)
num=input().split()
a=int(num[0])
b=int(num[1])
if a!=b:
  print(max([a+b,a-b,a*b]))
else:
  print(max([a+b,a-b,a*b,a/b]))

### FIXED CODE ###

num=input().split()
a=int(num[0])
b=int(num[1])
print(max([a+b,a-b,a*b]))
x,y = input().split()
a,b = ord(x), ord(y)
 
if a < b:
    print('<')
elif a > b:
    print('>')
else if a = b:
    print('=')

### FIXED CODE ###

a,b=input().split()
x,y=ord(a),ord(b)

if x > y:
    print(">")
elif x==y:
  print("=")
else:
  print("<")
import math

a, b = map(int, input().split())  # 複数数値入力

A = list()
B = list()

if b == 0:
    B = [0]
elif b == 1:
    B = [1]
else:
    for i in range(1, int(math.log2(b))+2):
        tmp = b // (2 ** i) * 2 ** (i - 1)

        if b % (2 ** i) < (2 ** (i-1)):
            plus = 0
        else:
            plus = b % (2 ** i) - 2 ** (i-1) + 1

        B.append(tmp + plus)

if a == 0:
    A = [0]
elif a == 1:
    A = [0]
else:
    for i in range(1, int(math.log2(a-1))+2):
        tmp = (a-1) // (2 ** i) * 2 ** (i - 1)

        if (a-1) % (2 ** i) < (2 ** (i-1)):
            plus = 0
        else:
            plus = (a-1) % (2 ** i) - 2 ** (i-1) + 1

        A.append(tmp + plus)

ans = 0
for i in range(0, int(math.log2(b)) + 1):
    print(i)
    if i >= len(A):
        ans += (B[i]) % 2 * 10 ** i
    else:
        ans += (B[i] - A[i]) % 2 * 10 ** i

print(int(str(ans), 2))


### FIXED CODE ###

import math

a, b = map(int, input().split())  # 複数数値入力

A = list()
B = list()

if b == 0:
    B = [0]
elif b == 1:
    B = [1]
else:
    for i in range(1, int(math.log2(b))+2):
        tmp = b // (2 ** i) * 2 ** (i - 1)

        if b % (2 ** i) < (2 ** (i-1)):
            plus = 0
        else:
            plus = b % (2 ** i) - 2 ** (i-1) + 1

        B.append(tmp + plus)

if a == 0:
    A = [0]
elif a == 1:
    A = [0]
else:
    for i in range(1, int(math.log2(a-1))+2):
        tmp = (a-1) // (2 ** i) * 2 ** (i - 1)

        if (a-1) % (2 ** i) < (2 ** (i-1)):
            plus = 0
        else:
            plus = (a-1) % (2 ** i) - 2 ** (i-1) + 1

        A.append(tmp + plus)

if b == 0:
    print(0)
else:
    ans = 0
    for i in range(0, int(math.log2(b)) + 1):
        if i >= len(A):
            ans += (B[i]) % 2 * 10 ** i
        else:
            ans += (B[i] - A[i]) % 2 * 10 ** i

    print(int(str(ans), 2))
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = []
    h2 = []

    for i in range(2 ** (n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & bit:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = ta * mb - tb * ma
        h1.append((dif,tc))

    for i in range(2 ** (n - n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n - n//2):
            if i & bit:
                a,b,c = med[j+n//2]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = tb * ma - ta * mb
        h2.append((dif,tc))

    h1.sort()
    h2.sort()
    i = 0
    ans = INF
    for h,c in h1:
        while h2[i][0] < h:
            i += 1
            if i >= len(h2): break
        else:
            while h2[i][0] == h:
                if h != 0 and h2[i][0] != 0:
                    ans = min(ans,c+h2[i][1])
                i += 1
            continue
        break
    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    n,ma,mb = LI()
    med = [LI() for _ in range(n)]
    h1 = [INF] * 10000

    for i in range(1,2 ** (n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n//2):
            if i & bit:
                a,b,c = med[j]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = ta * mb - tb * ma
        if h1[dif] > tc: h1[dif] = tc

    ans = h1[0]

    for i in range(1,2 ** (n - n//2)):
        bit = 1
        ta = 0
        tb = 0
        tc = 0
        for j in range(n - n//2):
            if i & bit:
                a,b,c = med[j+n//2]
                ta += a
                tb += b
                tc += c
            bit <<= 1
        dif = tb * ma - ta * mb
        if dif == 0:
            ans = min(ans,tc)
        else:
            ans = min(ans,h1[dif]+tc)

    if ans < INF:
        print(ans)
    else:
        print(-1)

if __name__ == '__main__':
    main()
i = 1
x = int(input())
for y in x:
    if y == 0:
        break
    if i == 10000:
        break
    print(f 'Case {i}: {y}')
    i += 1



### FIXED CODE ###

case_num = 1

while True:
    tmp_num = int(input())
    if tmp_num == 0:
        break
    else:
        print("Case %d: %d" % (case_num,tmp_num))
        case_num += 1
MOD = 10**9 + 7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]

aa = [True] * (N+1)
for i in a:
    aa[i] = False

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 0
if aa[1]:
    dp[1] = 1

for i in range(2,N+1):
    if (aa[i] == False):
        dp[i] = 0
        continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= MOD
print(dp[i])


### FIXED CODE ###

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

MOD = 10**9 + 7

safe = [True] * (N+1)
for i in range(len(A)):
    safe[A[i]] = False

dp = [0] * (N+1)
dp[0] = 1
if safe[1]:
    dp[1] = 1

for i in range(2, N+1):
    if(safe[i]):
        dp[i] = dp[i-1] + dp[(i-2)]
        dp[i] = dp[i] % MOD
    else:
        dp[i] = 0

print(dp[N])
import sys
if __name__ == "__main__":
    N = int(input())
    drow_lst = [59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
#    drow_lst = [7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1]
    min = 1000000
    buf_lst = []
    for ele in drow_lst:
        if ele <= N:
            buf_lst.append(ele)
    drow_lst = buf_lst
    for i in range(len(drow_lst)):
        cnt = 0
        buf = N
        buf_drow_lst = drow_lst[i:len(drow_lst)]
        check = []
#        print(buf_drow_lst)
        for ele in buf_drow_lst:
#            print("buf"+str(buf))
#            print("ele"+str(ele))
            if buf % 9 == 0:
                check_buf = cnt + (buf // 9)
                check.append(check_buf)
            if buf % 6 == 0:
                check_buf = cnt + (buf // 6)
                check.append(check_buf)
            if buf >= ele:
                cnt += buf // ele
#                print("cnt"+str(cnt))
                buf = buf % ele
        if min > cnt:
            min = cnt
#        print(check)
        if len(check) > 0 and min > min(check):
            min = min(check)
    print(min)

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()

dp = [99999999] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
    dp[i] = dp[i - 1] + 1
    k = 6
    while i - k >= 0:
        dp[i] = min(dp[i], dp[i - k] + 1)
        k *= 6
    k = 9
    while i - k >= 0:
        dp[i] = min(dp[i], dp[i - k] + 1)
        k *= 9
print(dp[n])
def count(list):
    a,b,z=0,0,0
    for i in range(len(list)):
        if list[i][0]=='B':
            b+=1
        if list[i][-1]=='A':
            a+=1
        
    if a==b==len(list):
        return a-1
    else:
        
        return min(a,b)
def check(string):
    c=0
    for i in range(len(string)-1):
        if string[i]=='A' and string[i+1]=='B':
            c+=1
    return c
n=int(input())
m,l=0,[]
for i in range(n):
    s=input()
    m+=check(s)
    
    l.append(s)
m+=count(l)
 
print(m)


### FIXED CODE ###

m=list(map(int, input().strip().split()))
print(m[0]-m[1]+1)
import numpy as np

N, D = list(map(int, input().split()))
X = []
for i in range(D):
    x_i = [int(i) for i in input().split()]
    X.append(i)
X = np.array(X)

ans = 0
for i in range(D):
    for j in range(i + 1, D):
        if np.sqrt(np.sum(X[i] - X[j]) ** 2).is_integer():
            ans += 1
print(ans)


### FIXED CODE ###

import numpy as np

def main():
    N, D = list(map(int, input().split()))
    X = []
    for i in range(N):
	    line = [int(a) for a in input().split()]
	    X.append(line)
    X_np = np.array(X)

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if(is_dist_int(X_np, D, i, j)):
                ans += 1
    print(ans)

def is_dist_int(X_np, D, i, j):
    dif = np.sum(np.square(np.abs(X_np[i] - X_np[j])))
    dis = np.sqrt(dif)
    return dis.is_integer()

main()
import sys
import math

for line in sys.stdin:
    a, b = map(int, line.split(' '))
    gcd = math.gcd(a, b)
    print(gcd, a * b // gcd)

### FIXED CODE ###

# Aizu - 0005
def De(a):
    res = []
    tmp = 2
    while a != 1:
        while not (a % tmp):
            a = round(a / tmp)
            res.append(tmp)
        tmp += 1
    return res

while True:
    try:
        tmp = input()
        a = [int(i) for i in tmp.split(' ')]
    except:
        break
    b = De(a[1])
    a = De(a[0])
    pa, pb = 0, 0
    GCD, LCM = 1, 1
    while True:
        if pa == len(a):
            for i in range(pb, len(b)):
                LCM *= b[i]
            break;
        if pb == len(b):
            for i in range(pa, len(a)):
                LCM *= a[i]
            break;
        if a[pa] == b[pb]:
            GCD *= a[pa]
            LCM *= a[pa]
            pa += 1
            pb += 1
            continue
        if a[pa] < b[pb]:
            LCM *= a[pa]
            pa += 1
            continue
        if a[pa] > b[pb]:
            LCM *= b[pb]
            pb += 1
            continue
    print('%d %d'%(GCD, LCM))
x, n = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
if n == 0:
    ans = x
else:
    p = sorted(p)
    min_p = min(p)
    max_p = max(p)
    j = 0
    ans = 0
    if x < min_p:
        ans = x
    elif x > max_p:
        ans = x
    elif x == min_p:
        if min_p+1 == p[1]:
            ans = min_p-1
        else:
            ans = min_p+1
    elif x == max_p:
        if max_p-1 == p[len(p)-2]:
            ans = max_p+1
        else:
            ans = max_p-1
    else:
        for i in range(min_p+1, max_p):
            if i == p[j+1]:
                j += 1
            else:
                if abs(ans-x) > abs(i-x):
                    ans = i
print(ans)

### FIXED CODE ###

x, n = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
if n == 0:
    ans = x
else:
    p = sorted(p)
    min_p = min(p)
    max_p = max(p)
    j = 0
    ans = 0
    if x < min_p:
        ans = x
    elif x > max_p:
        ans = x
    elif x == min_p:
        ans = min_p-1
    elif x == max_p:
        if max_p-1 == p[len(p)-2]:
            ans = max_p+1
        else:
            ans = max_p-1
    else:
        for i in range(min_p-1, max_p+1):
            if i == p[j]:
                j += 1
                if len(p) == j:
                    im_i = p[j-1] +1
                    if abs(ans-x) > abs(im_i-x):
                        ans = im_i
            else:
                if abs(ans-x) > abs(i-x):
                    ans = i
print(ans)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)


def memoize(f):
    memo = dict()

    def memoized(*args):
        if args in memo.keys():
            return memo[args]
        else:
            memo[args] = f(*args)
            return memo[args]
    return memoized

@memoize
def longest_path(v):
    retval = 0
    for v2 in edges[v]:
        retval = max(retval, longest_path(v2)+1)
    return retval


ans = 0
for i in range(n):
    ans = max(ans, longest_path(i))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)


def memoize(f):
    memo = dict()

    def memoized(*args):
        if args in memo.keys():
            return memo[args]
        else:
            memo[args] = f(*args)
            return memo[args]
    return memoized

@memoize
def longest_path(v):
    retval = 0
    for v2 in edges[v]:
        retval = max(retval, longest_path(v2)+1)
    return retval


ans = 0
for i in range(n):
    ans = max(ans, longest_path(i))
print(ans)
import sys
import collections

ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n = ri()
a = rl()
il = list(set(a))
li = collections.Counter(a)
q = ri()
res = []
for _ in range(q):
    b, c = rm()
    if b in il:
        if c in il:
            li[c] += li[b]
        else:
            li[c] = li[b]
            il.append(c)
        li[b] = 0
        il.remove(b)
    ans = 0
    for k, v in li.items():
        ans += k*v
    res.append(ans)
for aaa in res:
    print(aaa)



### FIXED CODE ###

import sys
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n = ri()
a = rl()
t = sum(a)
cnt_li = [0]*10**5
for i in a:
    cnt_li[i-1] += 1

for _ in range(ri()):
    b, c = rm()
    t += (c-b)*cnt_li[b-1]
    print(t)
    cnt_li[c-1] += cnt_li[b-1]
    cnt_li[b-1] = 0
n=int(input())
s=int(input())
rootn=0
while rootn**2<=n:
    rootn+=1

    
def fun(b,n):
    if n<b:return n
    elif n>=b:
        return fun(b,n//b)+n%b
def main(n,s):
    if n==s:return n+1
    for b in range(2,rootn):
        if fun(b,n)==s:return int(b)
    
    for p in reversed(range(1,rootn)):
        b=1+(n-s)//p
        if fun(b,n)==s:return int(b)
        b=2+(n-s)//p
        if fun(b,n)==s:return int(b)
    return -1

x=main(n,s)
print(x)
#http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf

### FIXED CODE ###

#ABC044D
def fun(b,n):
    if n<b:return n
    return (n%b)+fun(b,n//b)
n=int(input())
s=int(input())
n_root=n**0.5

def main(n,n_root,s):
    if s==n:return n+1
    if s>n:return -1
    if (n//2)+1<s:return -1
    for b in range(2,1+int(n_root)):
        if fun(b,n)==s:
            return b
    for i in range(int(n_root),0,-1):
        b=1+(n-s)//i
        if fun(b,n)==s:
            if b>1:return b
    return -1
print(main(n,n_root,s))
for i in a:
    if i%2==0:
        k +=1
m=n-k

ans_x=ans_y=0

def cbn(b,c):
    z=1
    for i in range(2,b+1):
        z *= i
    for i in range(2,c+1):
        z //= i
    for i in range(2,b-c+1):
        z //= i
    return(z)


if p==0:

    for i in range(k+1):
        ans_x += cbn(k,i)
    for i in range(0,m+1,2):
        ans_y += cbn(m,i)

    print(ans_x * ans_y)

else:

    for i in range(k+1):
        ans_x += cbn(k,i)
    for i in range(1,m+1,2):
        ans_y += cbn(m,i)

    print(ans_x * ans_y) 

### FIXED CODE ###

n,p=map(int,input().split())
a=list(map(int,input().split()))
k=m=0
for i in a:
    if i%2==0:
        k +=1
m=n-k

ans_x=ans_y=0

def cbn(b,c):
    z=1
    for i in range(2,b+1):
        z *= i
    for i in range(2,c+1):
        z //= i
    for i in range(2,b-c+1):
        z //= i
    return(z)


if p==0:

    for i in range(k+1):
        ans_x += cbn(k,i)
    for i in range(0,m+1,2):
        ans_y += cbn(m,i)

    print(ans_x * ans_y)

else:

    for i in range(k+1):
        ans_x += cbn(k,i)
    for i in range(1,m+1,2):
        ans_y += cbn(m,i)

    print(ans_x * ans_y)
#coding:utf-8
n, m = map(int, input().split())
A = list(map(int, input().split()))
ll = []
for i in range(m):
    b, c = map(int, input().split())
    ll.extend([c] * b)
A.sort(reverse=True)
ll.sort(reverse=True)
i, j = 0, 0
ans = 0
for _ in range(n):
    if A[i] >= ll[j] and i < n:
        ans += A[i]
        i += 1
    elif A[i] < ll[j] and j < n:
        ans += ll[j]
        j += 1
    else:
        ans += A[i]
        i += 1
print(ans)

### FIXED CODE ###

# coding: utf-8
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
minus = 0
l = []
for i in range(M):
    b, c = map(int, input().split())
    l.append([b, c])
l.sort(key=lambda x: x[1], reverse=True)
A.sort(reverse=False)
idx = 0
i = 0
ans = 0
while i < N and idx < M:
    if l[idx][0] == 0:
        idx += 1
    if idx >= M:
        ans += A[i]
        i += 1
        continue
    if A[i] < l[idx][1]:
        ans += l[idx][1]
        l[idx][0] -= 1
        i += 1
    else:
        ans += A[i]
        i += 1
    # print("ans =", ans)
for j in range(i, N):
    ans += A[j]
print(ans)
from collections import*
from heapq import*
def dijkstra(s):
  d=[inf]*n
  used=[True]*n
  d[s]=0
  used[s]=False
  edgelist=[]
  for e in edge[s]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  return d
inf=10**18
n,m,*t=map(int,open(0).read().split())
e=defaultdict(list)
s=set()
l=set()
f=False
for a,b,c in zip(t[::3],t[1::3],t[2::3]):
  if b<a:a,b=b,a
  if a<2 or b<2:f=True
  x,y=a+-~n*c,b+-~n*c
  if b==n:l|={y}
  e[a].append((1,x))
  e[b].append((1,y))
  e[x].extend([(0,a),(0,y)])
  e[y].extend([(0,b),(0,x)])
  s|=set((a,b,x,y))
if not f:
  print(-1)
  exit()
d={i:v for v,i in enumerate(sorted(s))}
n=len(d)
edge=tuple([]for _ in range(n))
for i in e:
  edge[d[i]].extend([(c,d[j])for c,j in e[i]])
a=dijkstra(0)
a=min(a[d[i]]for i in l)
print([a,-1][a==inf])

### FIXED CODE ###

def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z={i:v for v,i in enumerate(sorted(set(z)))}
  try:
    z[1]
  except:
    print(-1)
    exit()
  edge=[[]for _ in range(len(z))]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
    if b==n:
      l.append(y)
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[False]+[True]*~-len(z)
  d=[0]+[inf]*~-len(z)
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()