Harryxun/stf_run huggingface dataset:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and q>0 and a[q]+a[p]<=md:
            p+=1
    except:
        p=n

    cnt+=n-p
    ans+=a[q]*(n-p)*2
    if p==n: break


ans+=(m-cnt)*md
print(ans)

### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
s = input()
s_len = len(s)

def judge(start=0, end=s_len)
  for i in range(start, end):
    if s[start+i] == s[end-1-i]:
      continue
    else:
      return 1
  return 0

if not judge() and not judge(end=(s_len-1)//2) and not judge(start=(s_len+3)//2-1):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s = input()
s_len = len(s)
 
def judge(start=0, end=s_len):
  for i in range(start, end):
    if s[i] == s[end-1-i]:
      continue
    else:
      return 0
  return 1
 
if judge() and judge(end=(s_len-1)//2) and judge(start=(s_len+3)//2-1):
  print("Yes")
else:
  print("No")
n = int(intput())
s = []
for i in range(n):
  tmp = str(input())
  tmp.sort()
  s.append(tmp)

a = [0 for i in range(10**3)]
for i in range(2, 10**3):
  x = a[i-1] + (i-1)
  a.append(x)

ans = 0
for _ in list(set(s)):
  ans+= a[s.count(_)]
  
print(ans)

### FIXED CODE ###

alphabet = "abcdefghijklmnopqrstuvwxyz"


n = int(input())
res = dict()
for _ in range(n):
    s = str(input())
    freqency = [0 for _ in alphabet]
    for __ in s:
        freqency[alphabet.index(__)] += 1
    freq = "".join([str(___) for ___ in freqency])
    if freq not in res:
        res[freq] = 1
    else:
        res[freq] += 1

ans = 0
for value in res.values():
    ans += ((value-1)*value)/2
  
print(int(ans))
M1, D1 = map(int, input())
M2, D2 = map(int, input())
if M1 == M2:
  print(0)
else:
  print(1)
  

### FIXED CODE ###

M1, D1 = map(int, input().split())
M2, D2 = map(int, input().split())
if M1 == M2:
  print(0)
else:
  print(1)
a,b = map(int,input().split())
 
for i in range(10**10):
  if (int(i*0.08)/int(i*0.1)) == a/b:
    print(i)
    exit()

### FIXED CODE ###

import math
a,b = map(int,input().split())
sup = math.floor((a+1)/0.08)

for i in range(1,sup):
  if math.floor(i*0.08)== a and math.floor(i*0.1) == b:
    print(i)
    exit()
    
print(-1)
import math

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

m_r = min(r)
print(math.ceil(N/r) + 4)

### FIXED CODE ###

import math
N = int(input())
r = [int(input()) for _ in range(5)]

m_r = min(r)
print(math.ceil(N/m_r) + 4)
N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
def dfs(a, b, k):
	global ans

	if a == (N - 1) and b == (M - 1):
		return True

	if k < 0:
		return False

	if a < N and k >= A[a] and dfs(a + 1, b, k - A[a]):
		ans += 1
		return True

	if b < M and k >= B[b] and dfs(a, b + 1, k - B[b]):
		ans += 1
		return True

	return True

dfs(0, 0, K)
print(ans)

### FIXED CODE ###

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

a = [0]
for i in range(N):
    a.append(a[i] +  A[i])
b = [0]
for i in range(M):
    b.append(b[i] + B[i])

ans = 0
j = M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
import sys
N = int(input())
input = sys.stdin.readline
A = [int(input()) for i in range(N)]
B = sorted(A)
B.reverse()
for j in range(N):
  if A[j] == B[0]:
    print(B[1])
  else:
    print(B[0

### FIXED CODE ###

import sys
N = int(input())
input = sys.stdin.readline
A = [int(input()) for i in range(N)]
B = sorted(A)
B.reverse()
for j in range(N):
  if A[j] == B[0]:
    print(B[1])
  else:
    print(B[0])
import os, sys, re, math

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

match = [-1,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]
    if m <= 0:
        return ''

    max_v = '0'
    for a in A:
        tmp = doit(m - match[a])
        if m >= match[a] and tmp is not None:
            max_v = max(max_v, str(a) + doit(m - match[a]),key= lambda x: int(x))

    if max_v != '0':
        memo[m] = max_v
        return max_v
    else:
        return None

print(doit(N))


### FIXED CODE ###

import os, sys, re, math
sys.setrecursionlimit(100000)
N,M = list(map(int,input().split(' ')))
A = list(map(int,input().split(' ')))

match = [100,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]
    if m == 0:
        return ""

    ret = None
    for a in A:
        tmp = None
        if m - match[a] >= 0:
            tmp = doit(m - match[a])
            if tmp is not None:
                tmp = str(a) + tmp
                if ret is not None:
                    if len(ret) < len(tmp) or (len(ret) == len(tmp) and tmp > ret):
                        ret = tmp
                else:
                    ret = tmp

    memo[m] = ret
    return ret

print(doit(N))
s = [c for c in "AKIHABARA"]
L = []
for i in range(0, 2):
    for j in range(0, 2):
        for k in range(0, 2):
            for l in range(0, 2):
                if i == 0:
                    s[0] = "X"
                if j == 0:
                    s[4] = "X"
                if k == 0:
                    s[6] = "X"
                if l == 0:
                    s[8] = "X"
                while "X" in s:
                    s.remove("X")
                L.append(s)
                s = [c for c in "AKIHABARA"] #bitで書きたかった・・・。
S = [c for c in input()]
for el in L:
    if S == el:
        print("YES")
        sys.exit(0)
print("NO")

### FIXED CODE ###

import sys
s = [c for c in "AKIHABARA"]
L = []
for i in range(0, 2):
    for j in range(0, 2):
        for k in range(0, 2):
            for l in range(0, 2):
                if i == 0:
                    s[0] = "X"
                if j == 0:
                    s[4] = "X"
                if k == 0:
                    s[6] = "X"
                if l == 0:
                    s[8] = "X"
                while "X" in s:
                    s.remove("X")
                L.append(s)
                s = [c for c in "AKIHABARA"] #bitで書きたかった・・・。
S = [c for c in input()]
for el in L:
    if S == el:
        print("YES")
        sys.exit(0)
print("NO")
a=int(input())
b=int(input())
c=int(input())
if a==b:
    if b==c: 
        print('NO')
    else:
        print('YES')
elif b==c:
    if a==c: 
        print('NO')
    else:
        print('YES')
elif a==c:
    if b==c:
        print('NO')
    else:
        print('YES')
else:
    print('NO')



### FIXED CODE ###

from sys import stdin
import math

if __name__ == '__main__':
	n = stdin.readline()
	n = n.rstrip('\n')
	n = n.split(' ')
	n = [int(i) for i in n]
	n.sort()
	if (n[0] == n[1] and n[1] != n[2]) or (n[0] != n[1] and n[1] == n[2]):
		print('Yes')
	else:
		print('No')
lim = 1e18
n = int(input());
nums = list(map(int,str(input()).split(" ")))
ans = 1
for num in nums:
	if ans <= lim:
    	ans *= num
if ans > lim:
    print(-1)
else:
    print(int(ans))


### FIXED CODE ###

def main():
    lim = 1e18
    n = int(input())
    nums = list(map(int,str(input()).split(" ")))
    if 0 in nums:
        print(0)
        return
    ans = 1
    for num in nums:
        ans *= num
        if ans > lim:
            print(-1)
            return
    print(ans)
    return

main()
import math
  def comb(n, r):
  	return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))
  base = comb(n+m, n * 2) + comb(n+m, m * 2)
  print(base)


### FIXED CODE ###

n, m = map(int, input().split())
import math
def comb(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
print(comb(n + m, 2) - n * m)
K = int(input())
if K % 2 == 0 or K % 5 == 0:
    print(-1)
else:
    if K % 7 == 0:
        L = 9 * K / 7
    else:
        L = 9 * K
n = 1
P = 10 % L
while True:
    if P == 1:
        print(n)
        break
    n += 1
    P = (10 * P) % K

### FIXED CODE ###

K = int(input())
if K % 2 == 0 or K % 5 == 0:
    print(-1)
    
else:
    if K % 7 == 0:
        L = 9 * K // 7
    else:
        L = 9 * K
    n = 1
    P = 10 % L
    while True:
        if P == 1:
            print(n)
            break
        n += 1
        P = (10 * P) % L
A, B, C, X = map(int, input().split())
I = 0
for i in range(A + 1):
	for j in range(B + 1):
		for k in range(C + 1):
			if 500 * i + 100 * j + 50 * k == X:
		I++
print(I)


### FIXED CODE ###

A=int(input())
B=int(input())
C=int(input())
X=int(input())

ans = 0
for a in range(A + 1):
    for b in range(B + 1):
        for c in range(C + 1):
            if 500 * a + 100 * b + 50 * c == X:
                ans += 1

print(ans)
#!/usr/bin/env python3
n = int(input())
a = [int(input()) for _ in range(n)]
#print(a)
cnt = [0]*(10**5)
for i in a:
    cnt[i-1] += 1
print(sum([1 for i in cnt if i % 2 == 1]))
exit(0)


### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
cnt = 1
ans = 0
for i in range(n-1):
    if a[i] == a[i+1]:
        cnt += 1
    else:
        if cnt %2: ans+= 1
        cnt = 1
print(ans+cnt%2)
from collections import deque
import numpy as np
n,k = map(int,input().split())
a = list(map(int,input().split()))
roop_find = deque([0])
i = 0
count = 0
while a[i]-1 not in roop_find:
    roop_find.append(a[i]-1)
    i = a[i] - 1
    count += 1
    if count == k:
        print(i + 1)
        break
    else:
        pass
if b <= k:
    b = roop_find.index(a[i]-1)
    roop = list(roop_find)[b:count+1]

    k -= b
    e = k % (count+1-b)
    print(roop[e]+1)


### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
pos = 0
visit = [0] * n
move = []
loop = []
while visit[pos] != 2:
    if visit[pos] == 0:
        move.append(pos)
    else:
        loop.append(pos)
    visit[pos] += 1
    pos = a[pos] - 1
if len(move) > k:
    print(move[k]+1)
else:
    print(loop[(k-(len(move)-len(loop)))%len(loop)]+1)
N=int(input())
S=str(input())
cnt=1

for i in range(len(S)):
  if S[i]==S[i+1]:
    continue
  else:
    cnt+=1

print(cnt)

### FIXED CODE ###

N=int(input())
S=str(input())
cnt=1

for i in range(len(S)-1):
  if S[i]==S[i+1]:
    continue
  else:
    cnt+=1
print(cnt)
S = input()
if s == "ABC":
  print("ARC")
else:
  print("ABC")

### FIXED CODE ###

S = input()
if S == "ABC":
  print("ARC")
else:
  print("ABC")
import sys
sys.setrecursionlimit(10**7)
mo=10**9+7

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

def P(n,k,mo):
    rt=1
    for i in range(k):
        rt*=(n-i)
        rt%=mo
    return rt

g=[[] for i in range(1+n)]
v=[0]*(1+n)
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)

def dfs(cur):
    c=len(g[cur])-1 #sum([v[i]!=1 for i in g[cur]])
    if c==0:
        return
    v[cur]=1
    ans[0]*=P(k-2,c,mo)
    for nb in g[cur]:
        if v[nb]!=1:
            dfs(nb)
v[1]=1
ans=[P(k,1+len(g[1]),mo)]

for j in g[1]:
    c=sum([v[i]!=1 for i in g[j]])
    ans*=P(k-2,c,mo)
    dfs(j)
print(ans[0]%mo)


### FIXED CODE ###

mo=10**9+7
n,k=map(int,input().split())

def P(n,k,mo):
    rt=1
    for i in range(k):
        rt*=(n-i)
        rt%=mo
    return rt

g=[[] for i in range(1+n)]
v=[0]*(1+n)

for i in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)

def dfs(cur):
    q=[]
    q.append(cur)

    while q:
        cur=q.pop()
        v[cur]=1
        c=len(g[cur])-1
        ans[0]*=P(k-2,c,mo)
        
        for nb in g[cur]:
            if v[nb]!=1:
                q.append(nb)
v[1]=1
ans=[P(k,1+len(g[1]),mo)]

for j in g[1]:
    dfs(j)
print(ans[0]%mo)
num1 = int(input())
num2 = int(input())
num3 = num1 + num2
num4 = num1 - num2
num5 = num1 * num2
num6 = [num3, num4, num5]
print(max(num6))

### FIXED CODE ###

num1,num2 = map(int,input().split())
 
num3 = num1 + num2
num4 = num1 - num2
num5 = num1 * num2
num6 = [num3, num4, num5]
 
print(max(num6))
S,f=__import__('collections').deque(input()),0
for _ in range(int(input())):
	T=input()
	if'2'>T:f=1-f
	else:S.insert(0if(T[2]<'2')^f else len(S),T[4])
if f:S.reverse()
print(*S,sep='')

### FIXED CODE ###

S,f=__import__('collections').deque(input()),0
for _ in range(int(input())):
	T=input()
	if T<'2':f=1-f
	else:(S.appendleft if (T[2]<'2')^f else S.append)(T[4])
if f:S.reverse()
print(*S,sep='')
#M num of prefecture
#N num of city
N, M = map(int,input().split())
#P pref
#Y year
P=[]
Y=[]
cities=[]
for i in range(M):
    try:
        s = input()
        p,y = s.split()
        city=(p,y)
        cities.append(city) 
        P.append(p)
        Y.append(y)
    except:
        break

sort_city=sorted(cities,key=lambda x:(x[0],x[1]))
prefs = sorted(set(P))

address=[]
res=[]
for i in range(len(sort_city)): 
    address=str(sort_city[i][0]).rjust(6,'0')+str(i+1).rjust(6,'0')
    res.append((sort_city[i],address))

print(res[1][0])
for i in range(len(cities)):
    for j in range(len(res)):
        if cities[i] == res[j][0]:
            print(res[j][1])
            break



### FIXED CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s=[]
for i in enumerate(l):
    s.append(i)
s=sorted(s,key=lambda x:(x[1][0],x[1][1]))
a=0
for i in range(m):
    if s[i][1][0]==0:
       a=1     
    elif s[i][1][0]==s[i-1][1][0]:
        a+=1
    elif s[i][1][0]!=s[i-1][1][0]:
        a=1
    s[i][1][1]=a
s = sorted(s,key=lambda x:x[0])
for i in s:
    print('%06d'%i[1][0]+'%06d'%i[1][1])
N = int(input())
def dfs(s): # 文字列 s で始まる七五三数の個数
    if int(s) > N:
        return 0
    ret = 1 if all(s.count(c) > 0 for c in '753') else 0 # s 自体が七五三数なら +1 for c in '753':
            ret += dfs(s + c)
    return ret
print(dfs('0')) # 本当は dfs('') と書きたいが 4 行目でのエラーを防ぐため仕方なく

#文字列をどんどん分岐しながら延ばすときにもdfsは使える
#準七五三数を全列挙し、それぞれについて判定


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

N = int(input())
def dfs(s): # 文字列 s で始まる七五三数の個数
    if int(s) > N:
        return 0
    ret = 1 if all(s.count(c) > 0 for c in '753') else 0 
    # s 自体が七五三数なら +1 
    for c in '753':
        ret += dfs(s + c)
    return ret
print(dfs('0')) # 本当は dfs('') と書きたいが 4 行目でのエラーを防ぐため仕方なく

#文字列をどんどん分岐しながら延ばすときにもdfsは使える
#準七五三数を全列挙し、それぞれについて判定
c = 0
while True:
    a = raw_input()
    if a == 0: break
    c += 1
    print 'Case %d: %d' %(c, a)

### FIXED CODE ###

c = 0
while True:
    a = raw_input()
    if a == '0': break
    c += 1
    print 'Case %d: %s' %(c, a)
import sys
N, Y = map(int, input().split())
for a in range(N+1):
    for b in range(N+1):
        c = N - a - c
        if c < 0:
            continue
        if 10000*a + 5000*b + 1000*c == Y:
            print(str(a)+" "+str(b)+" "+sstr(c))
            sys.exit()
print("-1 -1 -1")

### FIXED CODE ###

N, Y = map(int, input().split())
result = [-1, -1, -1]
for a in range(0, N+1):
    for b in range(0, N+1):
        c = N-a-b
        if c < 0:
            continue
        if Y == (10000*a + 5000*b + 1000*c):
            result[0] = a
            result[1] = b
            result[2] = c
print (" ".join(map(str, result)))
d=int(input())
for i in range(d):
   print(26%i+1)

### FIXED CODE ###

d=int(input())
c=list(map(int,input().split()))
c_days=[0]*26

fir_ans=0
for i in range(d):
    s=list(map(int,input().split()))
    ss=sorted(s, reverse=False)
    for k in range(26):
        num=ss[k]
        n=s.index(num)
        if c_days[n]==0:

            fir_ans+=num
            continue 
    c_days[n]=i+1
    print(n+1)
    '''
    for l in range(26):
        los=c[l]*(i+1-c_days[l])
        fir_ans-=los
    print(fir_ans)
    '''
N,x = map(int,input().split())
# a=[int(input()) for i in range(4)]
a = list(map(int,input().split()))
count = 0
#昇順に並べ替える
sort_a = sorted(a)

for i in range(len(N)):
    if x >= sort_a[i]:
        count += 1
        x -= sort_a[i]
        print(x)
        continue
    break
print(count)


### FIXED CODE ###

N,x = map(int,input().split())
a = list(map(int,input().split()))
count = 0
#昇順に並べ替える
# sort_a = sorted(a)
a.sort(reverse=False)
for i in range(N):
    if x >= a[i]:
        count += 1
        x -= a[i]
    else:
        break

if (x!=0)and(count == N):
    count -= 1
print(count)
import numpy as np

n = int(input())
r = []
b = []

for i in range(n):
    x,y = map(int,input().split())
    r.append([x,y])

for i in range(n):
    x,y = map(int,input().split())
    b.append([x,y])



r.sort(key=lambda x:[x[0],x[1]])
b.sort(key=lambda x:[x[0],x[1]])

r2 = r.copy()
b2 = b.copy()

r2.sort(key=lambda x:[x[1],x[0]])
b2.sort(key=lambda x:[x[1],x[0]])
# print(r)
# print(b)

ans = 0
for i in range(n):
    x,y = b[i][0],b[i][1]
    # print(x,y)
    tar = 0
    flag = False
    for j in range(len(r)):
        if r[j][0] < x and r[j][1] < y:
            flag = True
            tar = j
    if flag:
        ans += 1
        r.pop(tar)


ans2 = 0

for i in range(n):
    x,y = b2[i][0],b2[i][1]
    # print(x,y)
    tar = 0
    flag = False
    for j in range(len(r)):
        if r2[j][0] < x and r2[j][1] < y:
            flag = True
            tar = j
    if flag:
        ans2 += 1
        r2.pop(tar)

print(max(ans,ans2))

### FIXED CODE ###

import numpy as np

n = int(input())
r = []
b = []

for i in range(n):
    x,y = map(int,input().split())
    r.append([x,y])

for i in range(n):
    x,y = map(int,input().split())
    b.append([x,y])



r.sort(key=lambda x:[x[0],x[1]])
b.sort(key=lambda x:[x[1],x[0]])


ans = 0
for i in range(n):
    x,y = b[i][0],b[i][1]
    tar = 0
    flag = False
    # print(r)
    # print(b)
    for j in range(len(r)):
        if r[j][0] < x and r[j][1] < y:
            flag = True
            tar = j
    if flag:
        ans += 1
        r.pop(tar)

print(ans)
N = int(input())
A = list(map(int,input().split()))
m = max(A)
U = [0]*(m+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,m)+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,m+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
U = [0]*(10**6+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,10**6+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,10**6+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)
n=int(input())
S=str(input())
s=list(S)
i=1
while True:
    if s[i-1]==s[i]:
        s.pop(i)
        n -= 1
    else:
        i +=1
    if i >=n:
        break
print(len(s))


### FIXED CODE ###

n=int(input())
S=str(input())
s=list(S)
i=1
while True:
    if n ==1 or n==0:
        break
    if s[i-1]==s[i]:
        s.pop(i)
        n -= 1
    else:
        i +=1
    if i >= n:
        break
print(len(s))
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 1
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print('selected_input:\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), input().split() ) )
else:
    N,M =tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), input().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,ci))

vlist =[ [None,[]] for _ in range(N)]    

for e in elist:
    a,b,c = e
    vlist[a][1].append((a,b,-c))
        
s_loc,g_loc = 0, N-1

vlist[s_loc][0] = 0
#print(vlist)

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g0 = vlist[g_loc][0]            

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g1 = vlist[g_loc][0]  

if g0 != g1:
    print('inf')
else:
    print(-g0)

#print('res',g0,g1)
for v in vlist:
    #print(v)        
    pass

### FIXED CODE ###

import sys

INF = float('inf')

def Bellmanford(n, edges, r): #r: 始点
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1 and v == n-1:
                    return 'inf'
    
    return -d[n-1]
    

N, M = map(int, sys.stdin.readline().split())
Edges = [None] * M

for i in range(M):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    Edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(N, Edges, 0)

print(ans)