Harryxun/stf_run huggingface dataset:
a=[]
N = int(input())
for i in range(N):
    a.append(int(input()))
a=sorted(a)

if(len(a)==2):
    print(abs(a[0]-a[1]))
elif(len(a)==3):
    print(max(a[2] - a[1] + a[2] - a[0], a[1]-a[0] + a[2]-a[0]))
else:
    #----------------------------------------------------------------------
    def append2big(id1, id2):
        global bBeg
        global bEnd
        global s
        if (a[id1] - bBeg + a[id2] - bEnd < a[id2] - bBeg + a[id1] - bEnd):
            id1, id2 = id2, id1
        s+=a[id1] - bBeg + a[id2] - bEnd
        bBeg = a[id1]
        bEnd = a[id2]
    def append2small(id1, id2):
        global bBeg
        global bEnd
        global s
        if (bBeg - a[id1] + bEnd - a[id2] < bBeg - a[id2] + bEnd - a[id1]):
            id1, id2 = id2, id1
        s+=bBeg - a[id1] + bEnd - a[id2]
        bBeg = a[id1]
        bEnd = a[id2]
    def append1small(id):
        global bBeg
        global bEnd
        global s
        if (bBeg - a[id] > bEnd - a[id]):
            s+=bBeg-a[id]
            bBeg = a[id]
        else:
            s+=bEnd-a[id]
            bEnd = a[id]
    def append1big(id):
        global bBeg
        global bEnd
        global s
        if (a[id] - bBeg > a[id] - bEnd):
            s+=a[id]-bBeg
            bBeg = a[id]
        else:
            s+=a[id]-bEnd
            bEnd = a[id]
    # ----------------------------------------------------------------------
    s = a[N-2]-a[0] + a[N-1] - a[0]
    bBeg = a[N-2]
    bEnd = a[N-1]
    l = 0
    r = N-2
    cur = 0
    while(l<r-1):
        if(cur==0):
            if(l+2<r):
                append2small(l+1, l+2)
                l+=2
            elif(l+1<r):
                append1small(l+1)
                l+=1
            cur = 1-cur
        else:
            if(r-2>l):
                append2big(r-1, r-2)
                r-=2
            elif(r-1>l):
                append1big(r-1)
                r-=1
            cur = 1- cur
    r1 = s
    #-----case 2------
    s = a[N - 1] - a[0] + a[N - 1] - a[1]
    bBeg = a[0]
    bEnd = a[1]
    l = 1
    r = N - 1
    cur = 1
    while (l < r - 1):
        if (cur == 0):
            if (l + 2 < r):
                append2small(l + 1, l + 2)
                l += 2
            elif (l + 1 < r):
                append1small(l + 1)
                l += 1
            cur = 1 - cur
        else:
            if (r - 2 > l):
                append2big(r - 1, r - 2)
                r -= 2
            elif (r - 1 > l):
                append1big(r - 1)
                r -= 1
            cur = 1 - cur
    r2 = s

    print(max(r1, r2))

### FIXED CODE ###

s = input()
if(len(s)==2):
    print(s)
else:
    print(s[::-1])
N,K=map(int,input().split())
print(K*bool(N%K!==0)-N%K)

### FIXED CODE ###

N,K=map(int,input().split())
print(0 if N%K==0 else 1)
def is_sorted(l):
    for i in range(len(l)):
        if l[i] != i + 1:
            return False
    return True


def can_go(start, goal, sw, d):
    if d > M: return False
    if start == goal: return True

    for s in sw:
        if s[0] == start:
            if can_go(s[1], goal, sw, d + 1):
                return True
        elif s[1] == start:
            if can_go(s[0], goal, sw, d + 1):
                return True
    return False


def try_s(l, sw):
    count = 0
    for idx, c in enumerate(l):
        if idx == c:
            continue
        if can_go(idx, c, sw, 0):
            # print(str(c) + ' can go home')
            count += 1
    print(count)


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

swaps = []
for i in range(M):
    x, y = map(int, input().split())
    swaps.append((x-1, y-1))


p = list(map(lambda x: x - 1, p))
# print(p)
# print(swaps)


if is_sorted(p):
    print(len(p))
else:
    try_s(p, swaps)


### FIXED CODE ###

# https://atcoder.jp/contests/abc097/tasks/arc097_b

import itertools
from collections import Counter
from collections import defaultdict
import bisect

# Union find
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]  # 負の値の場合根を表す。絶対値はツリーの高さ 正の値は次の要素を返す、根まで続く
        self.size = [1 for _  in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.size[s1] += self.size[s2]
                else:
                    self.table[s1] = s2
                    self.size[s2] += self.size[s1]
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
                self.size[s1] += self.size[s2]
        return

    def group_size(self, x):
        return self.size[self.find(x)]


def main():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))

    uf = UnionFind(N+1)
    for _ in range(M):
        a, b = map(int, input().split())
        uf.union(a, b)

    ans = 0
    for i in range(N):
        if uf.is_same(i + 1, P[i]):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()
import heapq
n = int(input())
a = list(map(int, input().split()))

l = a[:n]
heapq.heapify(l)
memo_l = [0 for _ in range(n+1)]
memo_l[0] = sum(a[:n])

for i in range(1, n+1):
    memo_l[i] = memo_l[i-1]
    if l[0] < a[n+i-1]:
        x = heapq.heappop(l)
        heapq.heappush(l, a[n+i-1])
        memo_l[i] += a[n+i-1] - x


r = [-a[-i] for i in range(1, n+1)]
heapq.heapify(r)
memo_r = [0 for _ in range(n+1)]
memo_r[0] = sum(a[-n:])

for i in range(1, n+1):
    memo_r[i] = memo_r[i-1]
    if abs(x) > a[-n-i]:
        x = heapq.heappop(r)
        heapq.heappush(r, -a[-n-i])
        memo_r[i] += x + a[-n-i]


ans = - 10 ** 20
for i in range(n+1):
    ans = max(ans, memo_l[i] - memo_r[n-i])

print(ans)

### FIXED CODE ###

import heapq
n = int(input())
a = list(map(int, input().split()))

l = a[:n]
heapq.heapify(l)
memo_l = [0 for _ in range(n+1)]
memo_l[0] = sum(a[:n])

for i in range(1, n+1):
    memo_l[i] = memo_l[i-1]
    if l[0] < a[n+i-1]:
        x = heapq.heappop(l)
        heapq.heappush(l, a[n+i-1])
        memo_l[i] += a[n+i-1] - x


r = [-a[-i] for i in range(1, n+1)]
heapq.heapify(r)
memo_r = [0 for _ in range(n+1)]
memo_r[0] = sum(a[-n:])

for i in range(1, n+1):
    memo_r[i] = memo_r[i-1]
    if abs(r[0]) > a[-n-i]:
        x = heapq.heappop(r)
        heapq.heappush(r, -a[-n-i])
        memo_r[i] += x + a[-n-i]


ans = - 10 ** 20
for i in range(n+1):
    ans = max(ans, memo_l[i] - memo_r[n-i])

print(ans)
from math import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

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

l = lcm(ai) // 2
i = m // l
if i == 0:
    print(0)
    exit()
if i == 1:
    print(1)
    exit()
ans = int(bin(i)[:-1], 2) + 1

print(ans)


### FIXED CODE ###

from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

def f(x):
    cnt = 0
    for c in reversed(bin(x)):
        if c == '0':
            cnt += 1
        else:
            return cnt
    return cnt

n, m = map(int, input().split())
ai = list(map(lambda x: x//2 , list(map(int, input().split()))))

t = f(ai[0])
for i, a in enumerate(ai):
    if f(a) != t:
        print('0')
        exit()
    ai[i] = a >> t

m = m >> t

l = lcm(ai)
i = m // l
ans = (i + 1) // 2

print(ans)
5 5 7
Yes
N,L = map(int,input().split())
str_list=[]
final_str = ""
for i in range(N):
    str_list.append(input())
new_list = sorted(str_list)
for n in range(N):
    final_str += new_list[n]
print(final_str)
3 3

### FIXED CODE ###

N,L = map(int,input().split())
str_list=[]
final_str = ""
for i in range(N):
    str_list.append(input())
new_list = sorted(str_list)
for n in range(N):
    final_str += new_list[n]
print(final_str)
from collections import deque 
def k_sub():
    s=input()
    k=int(input())
    dq=deque()
    for i in range(1,len(s)+1):
        for j in range(k):
            a.append(s[j:j+i])
    a.sort()
    print(a[k-1])
if __name__=='__main__':
    k_sub()

### FIXED CODE ###

s=input()
k=int(input())

a=sorted({s[i:i+j+1] for i in range(len(s)) for j in range(k)})[k-1]
print(a)
import fractions
import copy
from functools import reduce

def l(i):
    if i==0:
        return 0
    else:
        return fractions.gcd(l(i-1),A[i-1])

def r(i):
    if i==N:
        return 0
    else:
        return fractions.gcd(r(i+1),A[i])

N=int(input())
A=[int(i) for i in input().split()]

ans=[]
if N==2:
    ans.append(max(A))
else:
    for i in range(N):
        ans.append(fractions.gcd(l(i),r(i+1)))

print(max(ans))

### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

import fractions
from functools import reduce

N=int(input())
A=[int(i) for i in input().split()]

def mygcd(a,b):
    if a==0:
        return b
    elif b==0:
        return a
    else:
        return fractions.gcd(a,b)

L=[0]*N
for i in range(1,N):
    L[i]=mygcd(L[i-1],A[i-1])

R=[0]*N
for i in range(N-2,-1,-1):
    R[i]=mygcd(R[i+1],A[i+1])

ans=1
for i in range(N):
    c=mygcd(L[i],R[i])
    ans=max(ans,c)

print(ans)
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab = sorted(ab, key = lambda x:x[1], reverse = True)
ab = sorted(ab)

def find_seed(ab, t):
	if len(ab) == 0:
		return 1
	if t[0] <= ab[0][0] < t[1]:
		t = [ab[0][0], min([ab[0][1],t[1]])]
		ab.pop(0)
		if len(ab) == 0:
			return 1
		else:
			return find_seed(ab,t)

	return 1

ans = 0

while len(ab) > 0:
	t = ab.pop(0)
	ans += find_seed(ab,t)

print(ans)

### FIXED CODE ###

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

c = E[0]
cnt = 0
for i in range(1,M):
	if c[0] <= E[i][0] < c[1]:
		c = [max(c[0],E[i][0]), min(c[1],E[i][1])]
	else:
		cnt += 1
		c = E[i]

print(cnt+1)
H, W =[int(i) for i in input().split()]
    if H==1 and W!=1:
      print(max(0, W-2))
    elif W==1 and H!=1:
      print(max(0, H-2))
    else:
      print(max(H-2, 0)*max(W-2, 0))

### FIXED CODE ###

H,W =[int(i) for i in input().split()]
if H*W==1:
    print(1)
elif H==1 and W!=1:
    print(max(0, W-2))
elif W==1 and H!=1:
    print(max(0, H-2))
else:
    print(max(H-2, 0)*max(W-2, 0))
import sys
from itertools import accumulate

N, Q = map(int, input().split())
S = input()
lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l-1, r])

t = [0] * N

for i in range(1, N):
    s = S[i-1:i+1]
    if s == 'AC':
        t[i] += 1

T = list(accumulate(t))
 
for i in lr:
    print(T[i[1]] - T[i[0]])

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
point = [list(map(int,input().split())) for i in range(Q)]
ac_list = [0]*(N+1)
 
for i in range(N):
  if S[i:i+2] == 'AC':
    ac_list[i+1] = ac_list[i] + 1
  else:
    ac_list[i+1] = ac_list[i]
 
 
for i in range(Q):
  print(ac_list[point[i][1]-1] - ac_list[point[i][0]-1])
n = int(input())
s == 0
for i in n:
  s += n[i]
if s % 9 == 0:
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

s = input()
sum = 0
for i in s:
  sum+=int(i)
if sum%9==0:
  print("Yes")
else:
  print("No")
import numpy as np

MOD = 10**9+7

D,T,E = input().split()
n= int(D)

arr = np.zeros((n+1,n+1),dtype=np.int16)
for i in range(3,n+1):
    arr[0,i] = 1









### FIXED CODE ###

D,T,S = [int(i) for i in input().split()]
out = 'Yes' if D <= T * S else 'No'
print(out)
n,x0=map(int,input().split())
x=list(map(int,input().split()))

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

ans=gcd(abs(x[0]-x0),abs(x[1]-x0))
for i in range(n):
    ans=gcd(ans,abs(x[i]-x0))
print(ans)

### FIXED CODE ###

n,x0=map(int,input().split())
x=list(map(int,input().split()))

def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
if n==1:
    ans=abs(x[0]-x0)
else:
    ans=gcd(abs(x[0]-x0),abs(x[1]-x0))
    for i in range(n):
        ans=gcd(ans,abs(x[i]-x0))
print(ans)
def comb(n,k):
  if n == 0:
    return 0
  if n == k:
    return 1
  
  num = 1
  for i in range(n-k+1,n+1):
    num *= i
    
  for i in range(2,k+1):
    num //= i
    

  return num
    
def syou(n,k):
  if k == 0:
    return 1
  
  if len(n) < k:
    return 0
  
  if len(n) == 1:
    return int(n)
  
  if n[0] == '0':
    return syou(n[1:l], k-1)
  
  l = len(n)
  ans = comb(l-1, k) * (9**k)
  
  top = int(n[0])
  ans += comb(l-1, k-1) * (top-1) * (9**(k-1))
  
  ans += syou(n[1:l], k-1)
  print('tmp:', n,k,ans)
  return ans


n = input()
k = int(input())

print(syou(n, k))

### FIXED CODE ###

def comb(n,k):
  if n == 0:
    return 0
  if n == k:
    return 1
  
  num = 1
  for i in range(n-k+1,n+1):
    num *= i
    
  for i in range(2,k+1):
    num //= i
    

  return num
    
def syou(n,k):
  if k == 0:
    return 1
  
  if len(n) < k:
    return 0
  
  if len(n) == 1:
    return int(n)
  
  l = len(n)
  if n[0] == '0':
    return syou(n[1:l], k)
  
  ans = comb(l-1, k) * (9**k)
  
  top = int(n[0])
  ans += comb(l-1, k-1) * (top-1) * (9**(k-1))
  
  ans += syou(n[1:l], k-1)
  return ans


n = input()
k = int(input())

print(syou(n, k))
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

def bsearch(arr, num):
    r = len(arr) - 1
    l = 0
    while r - l > 1:
        c = (r + l) // 2
        if arr[c] > num:
            r = c
        elif arr[c] < num:
            l = c
        else:
            l = c
            r = c
            break
    return [l, r]

n, q = MAP()
s = STR()
index = []
for i in range(len(s) - 1):
    if s[i] + s[i + 1] == 'AC':
        index.append(i)
ans = 0
for _ in range(q):
    l, r = MAP()
    ll = bsearch(index, l - 1)
    rr = bsearch(index, r - 2)
    lll = ll[0] if index[ll[0]] >= l - 1 else ll[1]
    rrr = rr[1] if index[rr[1]] <= r - 2 else rr[0]
    print(rrr - lll + 1)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, q = MAP()
s = STR()
arr = [1 if s[i] + s[i + 1] == 'AC' else 0 for i in range(n - 1)]
arr2 = [[0, False] for _ in range(n - 1)]
arr2[0] = [arr[0], True if arr[0] == 1 else False]
for i in range(1, n - 1):
    arr2[i][0] = arr2[i - 1][0] + arr[i]
    arr2[i][1] = True if arr[i] == 1 else False
for _ in range(q):
    l, r = MAP()
    print(arr2[r - 2][0] - arr2[l - 1][0] + arr2[l - 1][1])
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
cheby = []
for i in range(n):
    l = [xy[i][0]-xy[i][1],xy[i][0]+xy[i][1]]
    cheby.append(l)

xmax = 0
xmin = 10**10
ymax = 0
ymin = 10**10
for i in range(n):
    if cheby[i][0] > xmax :
        xmax = cheby[i][0]
        xa = i
    if cheby[i][0] < xmin :
        xmin = cheby[i][0]
        xi = i
    if cheby[i][1] > ymax :
        ymax = cheby[i][1]
        ya = i
    if cheby[i][1] < ymin :
        ymin = cheby[i][1]
        yi = i

if abs(xmax-xmin) > abs(ymax-ymin):
    print(abs(xy[xa][0]-xy[xi][0])+abs(xy[xa][1]-xy[xi][1]))
else :
    print(abs(xy[ya][0]-xy[yi][0])+abs(xy[ya][1]-xy[yi][1]))


### FIXED CODE ###

n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
cheby = []
for i in range(n):
    l = [xy[i][0]-xy[i][1],xy[i][0]+xy[i][1]]
    cheby.append(l)

xmax = -10**10
xmin = 10**10
ymax = -10**10
ymin = 10**10
for i in range(n):
    if cheby[i][0] > xmax :
        xmax = cheby[i][0]
        xa = i
    if cheby[i][0] < xmin :
        xmin = cheby[i][0]
        xi = i
    if cheby[i][1] > ymax :
        ymax = cheby[i][1]
        ya = i
    if cheby[i][1] < ymin :
        ymin = cheby[i][1]
        yi = i

if abs(xmax-xmin) > abs(ymax-ymin):
    print(abs(xy[xa][0]-xy[xi][0])+abs(xy[xa][1]-xy[xi][1]))
else :
    print(abs(xy[ya][0]-xy[yi][0])+abs(xy[ya][1]-xy[yi][1]))
A=input()
cnt={chr(code): 0 for code in range(ord('a'),ord('z')+1)}
for i in A:
  cnt[i]+=1

from math import factorial
def c(n,r):
  return factorial(n)/factorial(r)/factorial(n - r)
a=len(A)
if a==1:
  print(1)
  exit()
b=0
for i in cnt.values():
  if i>=2:
    b+=i*(i-1)//2
ans=int(c(a,2)-b)
print(ans+1)

### FIXED CODE ###

A=input()
cnt={chr(code): 0 for code in range(ord('a'),ord('z')+1)}
for i in A:
  cnt[i]+=1

a=len(A)
if a==1:
  print(1)
  exit()
b=0
for i in cnt.values():
  if i>=2:
    b+=i*(i-1)//2
ans=a*(a-1)//2-b
print(ans+1)
x,y,a,b,c = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort()
q.sort()
r.sort(reverse=True)

ppick = p[-x:]
qpick = q[-y:]

pi = 0
qi = 0

for i in range(len(r)):
    if pi >= a:
        while True:
            if r[i] > qpick[qi] and qi <= b and i <= c:
                qpick[qi] = r[i]
                qi += 1
                i += 1
            else:
                break
    elif qi >= b:
        while True:
            if r[i] > ppick[pi] and pi <= a and i <= c:
                ppick[pi] = r[i]
                pi += 1
                i += 1
            else:
                break
    elif ppick[pi] > qpick[qi] and qpick[qi] < r[i]:
        qpick[qi] = r[i]
        qi += 1
        continue
    elif ppick[pi] < qpick[qi] and ppick[pi] < r[i]:
        ppick[pi] = r[i]
        pi += 1
        continue
    break

print(sum(ppick) + sum(qpick))


### FIXED CODE ###

x,y,a,b,c = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

p.sort()
q.sort()
r.sort(reverse=True)

ppick = p[-x:]
qpick = q[-y:]
pi = 0
qi = 0

for i in range(len(r)):
    if pi >= x:
        while True:
            if qi < y and i < c and r[i] > qpick[qi]:
                qpick[qi] = r[i]
                qi += 1
                i += 1
            else:
                break
    elif qi >= y:
        while True:
            if pi < x and i < c and r[i] > ppick[pi]:
                ppick[pi] = r[i]
                pi += 1
                i += 1
            else:
                break
    elif ppick[pi] >= qpick[qi] and qpick[qi] < r[i]:
        qpick[qi] = r[i]
        qi += 1
        continue
    elif ppick[pi] < qpick[qi] and ppick[pi] < r[i]:
        ppick[pi] = r[i]
        pi += 1
        continue
    break

print(sum(ppick) + sum(qpick))
S = input()
N = len(S)
K = int(input())

S1 = {}
for i, s in enumerate(S):
    if not s in S1.keys():
        S1[s] = [i]
    else:
        S1[s].append(i)
alp = sorted(list(S1.keys()))

c = 0
for a in alp:
    aset = set()
    inds = S1[a]
    for d in inds:
        for i in range(N-d+1):
            aset.add(S[d:d+i])
    if len(aset)-1 >= K-c:
        break
    c += len(aset)-1


for _ in range(5):
    for i, a in enumerate(aset):
        if i == 0:
            min = a
            continue
        if a < min:
            min = a
    aset.discard(min)
    if min == '':
        continue
    c += 1
    if c >= K:
        ans = min
        break

print(ans)


### FIXED CODE ###

a, b, c, d = map(int, input().split())

if abs(c-a) <= d or (abs(b-a) <= d and abs(c-b) <= d):
    print('Yes')
else:
    print('No')
from math import inf
n, m = list(map(int, input().split()))
a, b, c = [], [], []
for _ in range(m):
    abc = list(map(int, input().split()))
    a.append(abc[0])
    b.append(abc[1])
    c.append(-abc[2]) # convert pos-neg

dist = [inf]*(n+1)
dist[1] = 0
for loop in range(n-1):
    for i in range(m):
        if dist[a[i]] == inf:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
ans = dist[-1]

negative = [False]*(n+1) # negative closed path
for loop in range(n):
    for i in range(m):
        if dist[a[i]] == inf:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True
        if negative[a[i]] is True:
            negative[b[i]] = True

# print(dist, negative)
if negative[-1] is True:
    print('inf')
else:
    print(-ans)

### FIXED CODE ###

INF = float('inf')
n, m = list(map(int, input().split()))
a, b, c = [], [], []
for _ in range(m):
    abc = list(map(int, input().split()))
    a.append(abc[0])
    b.append(abc[1])
    c.append(-abc[2]) # convert pos-neg

dist = [INF]*(n+1)
dist[1] = 0
for loop in range(n-1):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
ans = dist[-1]

negative = [False]*(n+1) # negative closed path
for loop in range(n):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True
        if negative[a[i]] is True:
            negative[b[i]] = True

    if negative[-1] is True:
        break
# print(dist, negative)
if negative[-1] is True:
    print('inf')
else:
    print(-ans)
N, W = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(W + 1):
        if j < w:
            dp[i][j] = max(dp[i][j], dp[i - 1][j])
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
print(dp[-1][-1])

### FIXED CODE ###

import numpy as np

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

dp = np.full(N * 1000 + 1, W + 1, dtype=np.int64)
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])

print(((dp <= W) * np.arange(N * 1000 + 1)).max())
from itertools import groupby
n=int(input())
h = list(map(int,input().split()))
p=[]
ans=[]
for i in range(n):
  if h[i] >= h[i+1]:
    p.append(1)
  else:
    p.append(0)
for key, value in groupby(p):
  ans.append(sum(value))
print(max(ans))

### FIXED CODE ###

from itertools import groupby
n=int(input())
h = list(map(int,input().split()))
p=[]
ans=[0]
for i in range(n-1):
  if h[i] >= h[i+1]:
    p.append(1)
  else:
    p.append(0)
for key, value in groupby(p):
  ans.append(sum(value))
print(max(ans))