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

from collections import deque
n = int(input())
edges = {}
lst = [[]for i in range(n)]
vert = [set() for i in range(n)]
ans = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = map(int,input().split())
    lst[a-1].append(b)
    lst[b-1].append(a)
    if a > b:
        a,b = b,a
    edges[(a,b)] = i
q = deque([1])
while q:
    x = q.popleft()
    q.extend(lst[x-1])
    for i in lst[x-1]:
        lst[x-1].remove(i)
        lst[i-1].remove(x)
        a = min(x,i)
        b = max(x,i)
        for j in range(1,n):
            if not (j in vert[x-1] or j in vert[i-1]):
                vert[x-1].add(j)
                vert[i-1].add(j)
                ans[edges[(a,b)]] = j
                break
print(max(ans))
for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(1,n):
    a,b = map(int,input().split())
    graph[a].append((i,b))
    graph[b].append((i,a))
colors = [0 for _ in range(n)]
parents = [0]*(n+1)
stack = [(1,0)]
while stack:
    x,c = stack.pop()
    color = 1
    for i,y in graph[x]:
        if parents[x] == y:
            continue
        else:
            parents[y] = x
            if color == c:
                color += 1
            colors[i] = color
            stack.append((y,color))
            color += 1
print(max(colors))
for i in range(1,n):
    print(colors[i])
### BUGGY CODE ###

A,B = map(int,input().split())
C = []
ans = 1
mid = int(max(A,B)/2)
for i in range(2,mid+2):
    if A % i== 0 and B % i == 0:
        C.append(i)
for i in range(0,len(C)):
    for j in range(2,C[i]+1):
        if j == C[i]:
            ans += 1
        elif C[i] % j == 0:
            break
print(ans)

### FIXED CODE ###

import math

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A,B = map(int,input().split())
a = prime_factorize(A)
b = prime_factorize(B)
ans = 1

while a != []:
    x = a[0]
    if x in b:
        ans+=1
    a = [i for i in a if i != x]

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

N,K=list(map(int,input().split(" ")))
A=list(map(int,input().split(" ")))
dp=[0]*N
for i in range(1,N):
  buf=10**100
  for j in range(1,K+1):
    if i-j<0:
      break
    buf=min((buf,dp[i-j]+abs(A[i-j]-A[i])))
  dp[i]=buf

print(dp[N-1])

### FIXED CODE ###

N,K=list(map(int,input().split(" ")))
A=list(map(int,input().split(" ")))
dp=[0]*N
for i in range(1,N):
  buf=10**100
  for j in range(1,K+1):
    if i-j<0:
      break
    buf=min((buf,dp[i-j]+abs(A[i-j]-A[i])))
  dp[i]=buf
 
print(dp[N-1])
### BUGGY CODE ###

n, p = map(int, input().split())
num = round(p ** (1 / n))
for i in range(num + 1, 0, -1):
    if p % (i ** n) == 0:
        print(i)
        break

### FIXED CODE ###

n,p = map(int,input().split())
dum = round(p**(1/n))
for i in range(dum,-1,-1):
    if p%(i**n) == 0:
        print(i)
        break
### BUGGY CODE ###

def f(n,x):
  ret = 0
  while n>0:
    n = (n+x-1)//x
    ret+=n
  return ret

n = int(input())
print(min(f(n,2), f(n,5)))

### FIXED CODE ###

def f(n):
  ans = 0
  while n>0:
    n//=5
    ans+=n
  return ans

x = int(input())
print(0 if x%2 else f(x//2))
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())

Sum = []
for a in range(1, K+1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            gcd = reduce(math.gcd, [a, b, c])
            Sum.append(gcd)

print(sum(Sum))

### FIXED CODE ###

import math

K = int(input())

Sum = []
for a in range(1, K+1):
    for b in range(1, K + 1):
        gcd2 = math.gcd(a, b)
        for c in range(1, K + 1):
            gcd = math.gcd(gcd2, c)
            Sum.append(gcd)

print(sum(Sum))
### BUGGY CODE ###

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

test = [0]*N

for i in range(M):
    A.sort()
    A[-1] = A[-1] // 2
    if A == test:
        break

total = sum(A)
print(total)


### FIXED CODE ###

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

test = [0]*N

A = list(map(lambda x: x*(-1) ,A))

import heapq

heapq.heapify(A)

for i in range(M):
    temp = ( heapq.heappop(A) * (-1) ) // 2 * (-1) 
    heapq.heappush(A,temp)
    if A == test:
        break

total = sum(A) * (-1)
print(total)
### BUGGY CODE ###

INF = -1000000000000001

n = int(input())
l = list(map(int, input().split()))

a = int(n/2)

dpa = [[INF]*(a+1) for i in range(n+1)]

dpa[0][0] = 0
dpa[1][0] = 0
dpa[1][1] = l[0]
j = 1
for i in range(2,n+1):
	if i == j*2:
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
	else:
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
		if (i != n):
			j += 1
#			print(i,j,dpa[i][j])
#			print("   ",i-2,j-1,dpa[i-2][j-1],"")
			dpa[i][j] = dpa[i-2][j-1]+l[i-1]

#print(dpa)
print(dpa[n][a])

### FIXED CODE ###

from collections import defaultdict
INF = -1000000000000001

n = int(input())
l = list(map(int, input().split()))

a = int(n/2)

dpa = defaultdict(lambda: -INF)
#dpa = [[0 for j in range(a+1)] for i in range(n+1)]

dpa[(0,0)] = 0
dpa[(1,0)] = 0
dpa[(1,1)] = l[0]
j = 1
for i in range(2,n+1):
	if i == j*2:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])
#		print(i,j,dpa[(i,j)])
	else:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])
#		print(i,j,dpa[(i,j)])
		if (i != n):
			j += 1
#			print(i,j,dpa[(i,j)])
#			print("   ",i-2,j-1,dpa[(i-2,j-1)],"")
			dpa[(i,j)] = dpa[(i-2,j-1)]+l[i-1]

#print(dpa)
print(dpa[n,a])
### BUGGY CODE ###

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

import itertools

comb = list(itertools.combinations(p, k))

ans = 100000000000
for i in range(len(comb)):
    ans = min(ans, sum(comb[i]))

print(ans)
    

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
p = sorted(p)

print(sum(p[0:k]))
### BUGGY CODE ###

import numpy as np
h,w=map(int,input().split())
m=np.empty((h,w),dtype="bool")
c=np.zeros((h,w),dtype="int16")
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==".":
            m[i][j]=True
        else:
            m[i][j]=False

for i in range(h):
    j=0
    start=-1
    while(j<w):
        if start==-1:
            if m[i][j]:
                start=j
                count=1
        else:
            if not m[i][j]:
                for k in range(start,j):
                    c[i][k]+=count
                start=-1
            else:
                count+=1
        j+=1
    if start!=-1:
        for k in range(start,w):
            c[i][k]+=count
for j in range(w):
    i=0
    start=-1
    while(i<h):
        if start==-1:
            if m[i][j]:
                start=i
                count=1
        else:
            if not m[i][j]:
                for k in range(start,i):
                    c[k][j]+=count
                start=-1
            else:
                count+=1
        i+=1
    if start!=-1:
        for k in range(start,h):
            c[k][j]+=count
result=0
for i in range(h):
    for j in range(w):
        result=max(result,c[i][j])
print(result-1)

### FIXED CODE ###

h,w=map(int,input().split())
m=[[None for j in range(w)] for i in range(h)]
c=[[-1 for j in range(w)] for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==".":
            m[i][j]=0
        else:
            m[i][j]=1

for i in range(h):
    j=0
    start=-1
    while(j<w):
        if start==-1:
            if m[i][j]==0:
                start=j
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,j):
                    c[i][k]+=count
                start=-1
            else:
                count+=1
        j+=1
    if start!=-1:
        for k in range(start,w):
            c[i][k]+=count
for j in range(w):
    i=0
    start=-1
    while(i<h):
        if start==-1:
            if m[i][j]==0:
                start=i
                count=1
        else:
            if m[i][j]==1:
                for k in range(start,i):
                    c[k][j]+=count
                start=-1
            else:
                count+=1
        i+=1
    if start!=-1:
        for k in range(start,h):
            c[k][j]+=count
result=0
for i in range(h):
    for j in range(w):
        result=max(result,c[i][j])
print(result)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    s = sorted(list(set(A)))

    for a in A:
        if len(s) == 1:
            print(s[-1])
        elif a == s[-1] and A.count(a) == 1:
            print(s[-2])
        else:
            print(s[-1])


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    s = sorted(list(set(A)))
    mc = A.count(s[-1])

    for a in A:
        if len(s) == 1:
            print(s[-1])
        elif a == s[-1] and mc == 1:
            print(s[-2])
        else:
            print(s[-1])


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

from functools import reduce
from math import gcd 

n = int(input())
A = list(map(int, input().split()))
pr = [True]*(10**6+5)
for a in A:
    vals = [i for i in range(2, a) if a % i == 0]
    for v in vals:
        for i in range(v, 10**6+2, v):
            if not pr[i]:
                break
            pr[i] = False
        else:
            continue
        break
    else:
        continue
    break
else:
    print('pairwise coprime')
    exit()

if reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

from functools import reduce
from math import gcd 

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

def furui(x):
    memo = [0]*(x+1)
    primes = []
    for i in range(2, x+1):
        if memo[i]: continue
        primes.append(i)
        memo[i] = i
        for j in range(i*i, x+1, i):
            if memo[j]: continue
            memo[j] = i
    return memo, primes

memo, primes = furui(10**6+5)

pr = [True]*(10**6+5)
for a in A:
    if a == 1: continue
    while a != 1:
        w = memo[a]
        if not pr[w]:
            break
        pr[w] = False
        while a%w == 0:
            a = a // w
    else:
        continue
    break
else:
    print('pairwise coprime')
    exit()

if reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

from sys import stdin
import numpy as np
n, k = map(int, stdin.readline().split())
a = np.array(stdin.readline().split(), dtype=np.int64)

ng = 0
ok = 10 ** 9 + 1
while ok - ng > 1:
    mid = (ok + ng) >> 1
    if sum(0 - - b // mid - 1 for b in a) <= k:
        ok = mid
    else:
        ng = mid
print(ok)


### FIXED CODE ###

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


def c(x):
    res = 0
    for b in a:
        # bを最大がxになるように、できるだけ少ない回数で
        # だいたいb/x等分？
        res += 0 - - b // x - 1
    return res <= k


ng = 0
ok = 10 ** 10
while ok - ng > 1:
    mid = (ok + ng) >> 1
    if c(mid):
        ok = mid
    else:
        ng = mid
print(ok)
### BUGGY CODE ###

"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_d

D - Knapsack 1
"""
INF = 100000007
import collections

def solve(wv_pairs):
    ws, vs = zip(*wv_pairs)
    dp = collections.defaultdict(lambda: -INF)
    dp[(-1, 0)] = 0
    for i in range(N):
        for ww in range(W + 1):
            dp[(i, ww)] = max(
                dp[(i - 1, ww)],
                dp[(i - 1, ww - ws[i])] + vs[i]
            )
    return max(dp[(N - 1, ww)] for ww in range(W + 1))

N, W = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(pairs)
print(res)


### FIXED CODE ###

"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_d

D - Knapsack 1
"""

def solve(wv_pairs):
    dp = [0] * (W + 1)
    for i in range(N):
        w_i, v_i = wv_pairs[i]
        for ww in range(W, w_i - 1, -1):
            dp[ww] = max(dp[ww], dp[ww - w_i] + v_i)
    return max(dp)


N, W = map(int, input().split())
pairs = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(pairs)
print(res)
### BUGGY CODE ###

H,W = list(map(int,input().split()))

A = [list(str(input())) for i in range(H)]

white = []
black = []

length = sum([a.count(".") for a in A])
cnt = 0

while (length > 0):
    gray = []
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                black.append([i,j])
            else:
                white.append([i,j])
       
    for l in white:
        if [l[0],l[1]-1] in black or [l[0],l[1]+1] in black or [l[0]-1,l[1]] in black or [l[0]+1,l[1]] in black:
            gray.append(l)

    for l in gray:
        black.append(l)
        white.remove(l)
        
    cnt += 1
    length = len(white)
    
print(cnt)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
A, B = [], []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
ans = 0
for i in range(N):
    L = []
    if i+1 not in A and i+1 not in B:
        ans += 1
    else:
        for j in range(M):
            if A[j] == i+1:
                if H[A[j]-1] != H[B[j]-1]:
                    L.append(H[A[j]-1])
                    L.append(H[B[j]-1])
            elif B[j] == i+1:
                if H[A[j]-1] != H[B[j]-1]:
                    L.append(H[A[j]-1])
                    L.append(H[B[j]-1])
        if len(L) == 0:
            d = 1
        elif max(L) == H[i]:
            ans += 1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
way=[[] for i in range(n)]
H = list(map(int,input().split()))
for i in range(m):
    a,b=map(int,input().split())
    way[a-1].append(b-1)
    way[b-1].append(a-1)
ans=0
for i in range(n):
    high=True
    for j in way[i]:
        if H[i]<=H[j]:
            high=0
            break
    if high:
        ans+=1
print(ans)
### BUGGY CODE ###

import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))


def solve1():
    que = []
    for a in A:
        for b in B:
            for c in C:
                heapq.heappush(que, -(a+b+c))
    for _ in range(k):
        print(-heapq.heappop(que))


solve1()


### FIXED CODE ###

import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

X, Y, Z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)


def calc(x, y, z):
    return [-A[x]-B[y]-C[z], x, y, z]


def solve1(A, B, C, X, Y, Z, k):
    Q = []
    Q.append(calc(0, 0, 0))

    ans = []
    # dict
    memo = {(0, 0, 0): True}
    for _ in range(k):
        e, x, y, z = heapq.heappop(Q)
        ans.append(-e)
        if x+1 < X and (x+1, y, z) not in memo:
            heapq.heappush(Q, calc(x+1, y, z))
            memo[(x+1, y, z)] = True
        if y+1 < Y and (x, y+1, z) not in memo:
            heapq.heappush(Q, calc(x, y+1, z))
            memo[(x, y+1, z)] = True

        if z+1 < Z and (x, y, z+1) not in memo:
            heapq.heappush(Q, calc(x, y, z+1))
            memo[(x, y, z+1)] = True

    print("\n".join(map(str, ans[:k])))


solve1(A, B, C, X, Y, Z, k)
### BUGGY CODE ###

K, S = [int(x) for x in input().split()]

dic = {}
for i in range(K + 1):
    for j in range (K + 1):
        r = S - i - j
        if r in dic.keys():
            dic[r].append((i, j))
        else:
            dic[r] = [(i, j)]

ans = 0
for k in range(K + 1):
    if k in dic.keys():
        ans += len(dic[k]) 

print(ans)

### FIXED CODE ###

K, S = [int(x) for x in input().split()]

ans = 0
for i in range(K + 1):
    for j in range (K + 1):
        r = S - i - j
        if r <= K and r >= 0:
            ans += 1
        
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)


class Warshall(object):
    """ 全てのノード間の最短路を計算する """
    def __init__(self, n:int):
        self.adjacency_dict = {}
        self.n = n
        for i in range(n):
            self.add_vertex(i)

            for j in range(n):
                if i == j:
                    self.adjacency_dict[i][j] = 0
                else:
                    self.adjacency_dict[i][j] = float('inf')

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = {}

    def add_edge(self, v1: int, v2: int, w: float, undirected=False):
        self.adjacency_dict[v1][v2] = w
        if undirected:
            self.adjacency_dict[v2][v1] = w

    def run(self):
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    self.adjacency_dict[i][j] = min(
                        self.adjacency_dict[i][j],
                        self.adjacency_dict[i][k] + self.adjacency_dict[k][j]
                    )


if __name__ == '__main__':
    N, M, L = map(int, input().split())

    g = Warshall(N)
    g2 = Warshall(N)
    for _ in range(M):
        v1, v2, w = map(int, input().split())
        if w <= L:
            g.add_edge(v1 - 1, v2 - 1, w, undirected=True)
            # g2.add_edge(v1 - 1, v2 - 1, 1, undirected=True)
    g.run()

    for i in range(N):
        for j in range(N):
            if g.adjacency_dict[i][j] <= L:
                g2.adjacency_dict[i][j] = 1
    g2.run()

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        ans = g2.adjacency_dict[s-1][t-1]
        if ans == float('inf'):
            print(-1)
        else:
            print(ans -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)
### BUGGY CODE ###

from random import randint

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

last = {}
ans = 0;

for _ in range(10**8):
    x = randint(0, n-1)
    y = randint(0, n-1)
    if abs(x-y) == a[x]+a[y] and last.get((x, y), "Hola") == "Hola":
        ans += 1;
        last[(x, y)] = 1;
        last[(y, x)] = 1;

print(ans)


### FIXED CODE ###

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

x = []
y = {}

for i, elem in enumerate(a):
    x.append(i+a[i])
    y[i-a[i]] = y.get(i-a[i], 0) + 1

ans = 0

for i in x:
    ans += y.get(i, 0)

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

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

a = [0] * m
b = [0] * m
c = [0] * m

for i in range(0,m):
    a[i], b[i], c[i] = map(int,input().split())
    a[i] = a[i] - 1
    b[i] = b[i] - 1
    c[i] = -c[i]

INF = 10 ** 12

dist = [INF] * n

dist[0] = 0

for j in range(0,n-1):
    for i in range(0,m):
        if dist[a[i]] == INF:
            continue
        dist[b[i]] = min(dist[b[i]], dist[a[i]] + c[i])

ans = - dist[n-1]

negative = [False] * n

for j in range(0,n):
    for i in range(0,m):
        if dist[a[i]] == INF:
            continue
        if dist[a[i]] + c[i] < dist[b[i]]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True
        elif negative[a[i]]:
            negative[b[i]] = True

if negative[n-1]:
    print("inf")
else:
    print(ans)
            




### FIXED CODE ###

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

a = [0] * m
b = [0] * m
c = [0] * m

for i in range(0,m):
    a[i], b[i], c[i] = map(int,input().split())
    a[i] = a[i] - 1
    b[i] = b[i] - 1
    c[i] = -c[i]

INF = (n-1) * max(abs(min(c)),abs(max(c)))

dist = [INF] * n

dist[0] = 0

for j in range(0,n-1):
    for i in range(0,m):
        if dist[a[i]] == INF:
            continue
        dist[b[i]] = min(dist[b[i]], dist[a[i]] + c[i])

ans = - dist[n-1]

negative = [False] * n

for j in range(0,n):
    for i in range(0,m):
        if dist[a[i]] == INF:
            continue
        if negative[a[i]]:
            negative[b[i]] = True
        elif dist[a[i]] + c[i] < dist[b[i]]:
            dist[b[i]] = dist[a[i]] + c[i]
            negative[b[i]] = True

if negative[n-1]:
    print("inf")
else:
    print(ans)