CodeEff/ECCO huggingface dataset:
# Original solution
import sys
from collections import Counter
 
inf = 1<<60
 
def solve():
    N, M = list(map(int, input().split()))
    edges = [None]*M
 
    for i in range(M):
        ui, vi, ci = list(map(int, sys.stdin.readline().split()))
        edges[i] = (ui-1, vi-1, -ci)
 
    ans = Bellmanford(N, M, edges)
 
    if ans is not None:
        print((-ans))
    else:
        print('inf')
 
def Bellmanford(N, M, edges):
    dist = [inf]*N
    dist[0] = 0
    flag = True
 
    while True:
        flag = False
 
        for (u, v, c) in edges:
            if dist[u] != inf and dist[v] > dist[u] + c:
                dist[v] = dist[u] + c
                flag = True
 
        # print(dist)
 
        if not flag or dist[0] < 0:
            break
 
    if dist[0] >= 0:
        return dist[N - 1]
    else:
        return None
 
if __name__ == '__main__':
    solve()

# Optimized solution
import sys
from collections import Counter

sys.setrecursionlimit(10**7)
 
inf = 1<<100
 
def solve():
    N, M = list(map(int, input().split()))
    edges = [None]*M
    Adj = [[] for i in range(N)]
 
    for i in range(M):
        ui, vi, ci = list(map(int, sys.stdin.readline().split()))
        ui, vi = ui - 1, vi - 1
        edges[i] = (ui, vi, -ci)
        Adj[ui].append(vi)

    visitable = [False]*N

    dfs(N, M, Adj, visitable, 0)

    reachable = [False]*N
    reachable[0] = True
    reachable[N - 1] = True

    for u in range(1, N - 1):
        visited = [False]*N

        dfs(N, M, Adj, visited, u)

        if visited[N - 1]:
            reachable[u] = True
 
    ans = Bellmanford(N, M, edges, visitable, reachable)
 
    if ans is not None:
        print((-ans))
    else:
        print('inf')

def dfs(N, M, Adj, visitable, u):
    visitable[u] = True

    for v in Adj[u]:
        if not visitable[v]:
            dfs(N, M, Adj, visitable, v)

def Bellmanford(N, M, edges, visitable, reachable):
    dist = [inf]*N
    dist[0] = 0
    flag = True

    cnt = 0
 
    for i in range(N):
        flag = False

        for (u, v, c) in edges:
            if dist[u] != inf and dist[v] > dist[u] + c:
                dist[v] = dist[u] + c

                if visitable[v] and reachable[v]:
                    flag = True

        # print(dist)

        if not flag:
            break

        if flag and i == N - 1:
            return None

    return dist[N - 1]
 
if __name__ == '__main__':
    solve()
# Original solution
import sys
from collections import Counter

sys.setrecursionlimit(10**7)
 
inf = 1<<100
 
def solve():
    N, M = list(map(int, input().split()))
    edges = [None]*M
    Adj = [[] for i in range(N)]
 
    for i in range(M):
        ui, vi, ci = list(map(int, sys.stdin.readline().split()))
        ui, vi = ui - 1, vi - 1
        edges[i] = (ui, vi, -ci)
        Adj[ui].append(vi)

    visitable = [False]*N

    dfs(N, M, Adj, visitable, 0)

    reachable = [False]*N
    reachable[0] = True
    reachable[N - 1] = True

    for u in range(1, N - 1):
        visited = [False]*N

        dfs(N, M, Adj, visited, u)

        if visited[N - 1]:
            reachable[u] = True
 
    ans = Bellmanford(N, M, edges, visitable, reachable)
 
    if ans is not None:
        print((-ans))
    else:
        print('inf')

def dfs(N, M, Adj, visitable, u):
    visitable[u] = True

    for v in Adj[u]:
        if not visitable[v]:
            dfs(N, M, Adj, visitable, v)

def Bellmanford(N, M, edges, visitable, reachable):
    dist = [inf]*N
    dist[0] = 0
    flag = True

    cnt = 0
 
    for i in range(N):
        flag = False

        for (u, v, c) in edges:
            if dist[u] != inf and dist[v] > dist[u] + c:
                dist[v] = dist[u] + c

                if visitable[v] and reachable[v]:
                    flag = True

        # print(dist)

        if not flag:
            break

        if flag and i == N - 1:
            return None

    return dist[N - 1]
 
if __name__ == '__main__':
    solve()

# Optimized solution
import sys

inf = 1<<60

def solve():
    N, M = list(map(int, input().split()))
    edges = [None] * M

    for i in range(M):
        ai, bi, ci = list(map(int, sys.stdin.readline().split()))
        ai, bi = ai - 1, bi - 1
        edges[i] = (ai, bi, -ci)

    ans = BellmanFord(N, M, edges)

    if ans is None:
        print('inf')
    else:
        print((-ans))

def BellmanFord(N, M, edges):
    d = [inf] * N
    d[0] = 0

    for i in range(N - 1):
        for (u, v, c) in edges:
            if d[u] + c < d[v]:
                d[v] = d[u] + c

    for i in range(N):
        for (u, v, c) in edges:
            if d[u] + c < d[v]:
                if v == N - 1:
                    return None

                d[v] = d[u] + c

    return d[N - 1]

if __name__ == '__main__':
    solve()
# Original solution
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
	a,b,c = inpl()
	a,b = a-1,b-1
	lines[a].add((b,-c))

def BellmanFord(Start,Goal):
	Costs=[INF]*N
	Costs[Start] = 0
	upd8s = [True]*N
	for i in range(N): #N回ループ(高々N-1回で収束する)
		will_upd8s = [False]*N
		upd8 = False
		for s in range(N):
			if not upd8s[s]: continue	#前回更新してないので見ない
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					will_upd8s[t] = True #更新した点だけ次に見る

		upd8s = will_upd8s[:]
		if not upd8:
			return Costs[Goal] #なにも更新しなかったら終わり
	else: #負回路の検出(もうN回)
		pc = Costs[Goal]
		for i in range(N):
			upd8 = True
			for s in range(N):
				for t,c in lines[s]:
					if c + Costs[s] < Costs[t]:
						Costs[t] = Costs[s]+c
						upd8 = True
			if not upd8: break

		if pc != Costs[Goal]:
			return -INF
		else:
			return Costs[Goal]

print((-BellmanFord(0,N-1)))


# Optimized solution
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)

for _ in range(M):
	a,b,c = inpl()
	a,b = a-1,b-1
	lines[a].add((b,-c))

#ベルマンフォード(始点と終点が決まってる時)
def BellmanFord(Start,Goal):
	Costs=[INF]*N
	Costs[Start] = 0
	upd8s = [True]*N
	for i in range(2*N): #2N回ループ(負回路の検出までみる)
		will_upd8s = [False]*N
		upd8 = False
		for s in range(N):
			if not upd8s[s]: continue	#前回更新してないので見ない
			for t,c in lines[s]:
				if c + Costs[s] < Costs[t]:
					Costs[t] = Costs[s]+c
					upd8 = True
					will_upd8s[t] = True #更新した点だけ次に見る

		if not upd8: #なにも更新しなかったら終わり
			return Costs[Goal]

		if i == N-1: #Nループ目のGoalのCostを記録
			tmp = Costs[Goal]

		upd8s = will_upd8s[:]

	if tmp != Costs[Goal]:
		return -INF
	else:
		return Costs[Goal]

print((-BellmanFord(0,N-1)))
# Original solution
N, M = list(map(int, input().split()))
a, b, c = [0] * M, [0] * M, [0] * M
d = [-1e20] * N
for i in range(M):
    a[i], b[i], c[i] = list(map(int, input().split()))
    a[i] -= 1
    b[i] -= 1

d[0] = 0
for i in range(N-1):
    for j in range(M):
        d[b[j]] = max((d[b[j]], d[a[j]] + c[j]))

isCycle = False
for i in range(N-1):
    if isCycle:
        break
    for j in range(M):
        if b[j] == N-1 and d[b[j]] < d[a[j]] + c[j]:
            isCycle = True
            break
        d[b[j]] = max((d[b[j]], d[a[j]] + c[j]))
if isCycle:
    print('inf')
else:
    print((d[N-1]))


# Optimized solution
N, M = list(map(int, input().split()))
a, b, c = [None] * M, [None] * M, [None] * M
INF = 1e14
d = [-INF] * N
d[0] = 0
for i in range(M):
    a[i], b[i], c[i] = list(map(int, input().split()))
    a[i] -= 1
    b[i] -= 1

for i in range(N):
    for j in range(M):
        if d[a[j]] + c[j] > d[b[j]]:
            d[b[j]] = d[a[j]] + c[j]
ans = d[N-1]
for i in range(N):
    for j in range(M):
        if d[a[j]] + c[j] > d[b[j]]:
            d[b[j]] = d[a[j]] + c[j]
if ans != d[N-1]:
    print('inf')
else:
    print(ans)
# Original solution
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u,s=0):
        route[u]=True
        memo[u]=s
        for v,c in ot[u]:
            if route[v]:
                if s+c>memo[v]:
                    return True
                continue
            if dfs(v,s+c):return True
            score[u]=max(score[u],score[v]+c)
        route[u]=False
        return False

    inf = 10 ** 14
    n, m = MI()
    ot = defaultdict(list)
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ot[b].append([a, c])

    score = [-inf] * n
    memo = [0] * n
    score[0]=0
    route=[False]*n
    if dfs(n-1):
        print("inf")
    else:
        print(score[n-1])

main()


# Optimized solution
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 14
    n, m = MI()
    ee = []
    # スコアの正負を逆にし、最小値を求める問題に置き換える
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ee.append([a, b, -c])
    # ベルマン・フォードで最小スコアを計算
    # n-1回やっても更新があるということは負の閉路があるということ
    # 負の閉路がなければ答えを出力して終了
    score = [inf] * n
    score[0] = 0
    for _ in range(n):
        change = False
        for a, b, c in ee:
            if score[a] + c < score[b]:
                score[b] = score[a] + c
                change = True
        if not change:
            print(-score[n - 1])
            exit()
    # 負の閉路がある場合は、その影響がゴールまで届くかをチェック
    reachable = [False] * n
    for _ in range(n):
        for a, b, c in ee:
            if reachable[a]:reachable[b]=True
            if score[a] + c < score[b]:
                score[b] = score[a] + c
                reachable[b] = True
        if reachable[n - 1]:
            print("inf")
            exit()
    print(-score[n-1])

main()
# Original solution
def main():
    N, M = list(map(int, input().split()))
    g = [[] for _ in range(N + 1)]
    d = [float('INF')] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        c = -c
        g[a].append((b, c))
    for i in range(2 * N):
        for x, r in enumerate(g):
            for y, c in r:
                if d[x] != float('INF') and d[y] > d[x] + c:
                    d[y] = d[x] + c
                    if y == N and i > N:
                        print("inf")
                        exit()

    print((-d[-1]))


main()


# Optimized solution
def main():
    N, M = list(map(int, input().split()))
    g = []
    d = [float('INF')] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        g.append((a, b, -c))
    for i in range(2 * N):
        for x, y, z in g:
            if d[x] != float('INF') and d[y] > d[x] + z:
                d[y] = d[x] + z
                if y == N and i > N:
                    print("inf")
                    exit()

    print((-d[-1]))


main()
# Original solution
def main():
    N, M = list(map(int, input().split()))
    g = []
    d = [float('INF')] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        g.append((a, b, -c))
    for i in range(2 * N):
        for x, y, z in g:
            if d[x] != float('INF') and d[y] > d[x] + z:
                d[y] = d[x] + z
                if y == N and i > N:
                    print("inf")
                    exit()

    print((-d[-1]))


main()


# Optimized solution
def main():
    N, M = list(map(int, input().split()))
    g = []
    INF = 10 ** 9 * 1000
    d = [INF] * (N + 1)
    d[1] = 0
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        g.append((a, b, -c))
    for i in range(2 * N):
        for x, y, z in g:
            if d[x] != INF and d[y] > d[x] + z:
                d[y] = d[x] + z
                if y == N and i > N:
                    print("inf")
                    exit()

    print((-d[-1]))


main()
# Original solution
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

def BELLMANFORD(point,d,n):
    cost       = [-float("inf")for node in range(n+1)]
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in list(d.items()):
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定
        for now,lis in list(d.items()):
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    negative[now-1]=1
 
    return cost,negative


def main():
    n,m=list(map(int,input().split()))
    
    d={}
    for s in range(m):
        a,b,c=list(map(int,input().split()))
        if a in d:
            d[a].append((b,c))
        else:
            d[a]=[(b,c)]
    
    x,y=(BELLMANFORD(1,d,n))
    
    if y[n-1]>0:
        print("inf")
    else:
        print((x[n]))


if __name__ == '__main__':
    main()


# Optimized solution
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！


def BELLMANFORD(point,n,d):
    cost=[1e18]*(n+1)
    cost[point]=0
    for i in range(n-1):
        for (nownode,nextnode,c) in d:
            if cost[nextnode]>cost[nownode]+c:  #infが定数なので論理が逆
                cost[nextnode]=cost[nownode]+c
    for (nownode,nextnode,c) in d:
        if cost[nextnode]>cost[nownode]+c:
            if nextnode==n:
                return "inf"
            cost[nextnode]=cost[nownode]+c
            
    return -cost[n]


def main():
    n,m=list(map(int,input().split()))
    
    d=[]
    for i in range(m):
        a,b,c=list(map(int,input().split()))
        d.append((a,b,-c))
    
    print((BELLMANFORD(1,n,d)))


if __name__ == '__main__':
    main()
# Original solution
from collections import deque
n,m = list(map(int,input().split()))
e1 = [[] for i in range(n)]
e2 = [[] for i in range(n)]
l = []
for i in range(m):
    a,b,c = list(map(int,input().split()))
    a -= 1
    b -= 1
    e1[a].append(b)
    e2[b].append(a)
    l.append([a,b,c])

def search(x,e):
    dis = [0]*n
    dis[x] = 1
    q = deque([])
    q.append(x)
    while q:
        now = q.popleft()
        for nex in e[now]:
            if dis[nex] == 0:
                dis[nex] = 1
                q.append(nex)

    return dis

dis1 = search(0,e1)
dis2 = search(n-1,e2)
dis = [0]*n
for i in range(n):
    if dis1[i] == 1 and dis2[i] == 1:
        dis[i] = 1

li = []
for i in range(m):
    a,b,c = l[i]
    if dis[a] == 1 and dis[b] == 1:
        li.append(l[i])

ans = [-float("INF")]*n
ans[0] = 0

for i in range(2*n):

    check = False
    for i,j,k in li:
        if ans[i]+k > ans[j]:
            ans[j] = ans[i]+k
            check = True
    
    if not check:
        print((ans[-1]))
        exit()
print("inf")

# Optimized solution
from collections import deque
n,m = list(map(int,input().split()))
e1 = [[] for i in range(n)]
e2 = [[] for i in range(n)]
l = []
for i in range(m):
    a,b,c = list(map(int,input().split()))
    a -= 1
    b -= 1
    e1[a].append(b)
    e2[b].append(a)
    l.append([a,b,c])

def search(x,e):
    dis = [0]*n
    dis[x] = 1
    q = deque([])
    q.append(x)
    while q:
        now = q.popleft()
        for nex in e[now]:
            if dis[nex] == 0:
                dis[nex] = 1
                q.append(nex)

    return dis

dis1 = search(0,e1)
dis2 = search(n-1,e2)
dis = [0]*n
for i in range(n):
    if dis1[i] == 1 and dis2[i] == 1:
        dis[i] = 1

li = []
for i in range(m):
    a,b,c = l[i]
    if dis[a] == 1 and dis[b] == 1:
        li.append(l[i])

ans = [-float("INF")]*n
ans[0] = 0

for i in range(n):

    check = False
    for i,j,k in li:
        if ans[i]+k > ans[j]:
            ans[j] = ans[i]+k
            check = True
    
    if not check:
        print((ans[-1]))
        exit()
print("inf")
# Original solution
import sys


def input(): return sys.stdin.readline().strip()


N, M = (list)(list(map(int, input().split())))
edge = []

for _ in range(M):
    edge.append((list)(list(map(int, input().split()))))


inf = 10**15

d = [inf]*(N+1)
d[1] = 0
ans = inf
for i in range(N-1):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d

neg = [False]*(N+1)
for i in range(N):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d
            neg[b] = True
        if neg[a]:
            neg[b] = True

if neg[-1]:
    print('inf')
else:
    print((-d[-1]))


# Optimized solution
import sys


def input(): return sys.stdin.readline().strip()


N, M = (list)(list(map(int, input().split())))
edge = []

for _ in range(M):
    edge.append((list)(list(map(int, input().split()))))


inf = 10**15

d = [inf]*(N+1)
d[1] = 0
ans = inf
for i in range(N-1):
    for a, b, c in edge:
        c = -c
        new_d = d[a]+c
        if d[a] != inf and d[b] > new_d:
            d[b] = new_d

for a, b, c in edge:
    c = -c
    new_d = d[a]+c
    if d[b] > new_d:
        d[b] = new_d
        if b == N:
            print('inf')
            exit()
print((-d[-1]))
# Original solution
N,M = list(map(int,input().split()))
ABC = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
Eb = [{} for _ in [0]*N]
for a,b,c in ABC:
    E[a-1][b-1] = -c
    Eb[b-1][a-1] = -c

#0 -> N-1 経路上にない頂点を除く
V1 = [False]*N
V1[0] = True
q = [0]
qp = q.pop
qa = q.append
while q:
    i = qp()
    for j in E[i]:
        if V1[j]:continue
        qa(j)
        V1[j]=True
V2 = [False]*N
V2[-1] = True
qa(N-1)
while q:
    i = qp()
    for j in Eb[i]:
        if V2[j] or not V1[j]:continue
        qa(j)
        V2[j]=True
for i in range(N):
    if V1[i] and V2[i]:continue
    for j in Eb[i]:
        E[j].pop(i)

INFTY = 10**18
d = [INFTY]*N
d[0] = 0

def update():
    done = [False]*N
    done[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        di = d[i]
        for j,c in list(E[i].items()):
            d[j] = min(d[j],d[i]+c)
            if not done[j]:
                qa(j)
                done[j] = True
                
for _ in range(N-1):update()
dc = d[:]
update()
if dc!=d:
    print("inf")
else:
    print((-d[-1]))

# Optimized solution
def main():
    N,M = list(map(int,input().split()))
    ABC = [list(map(int,input().split())) for _ in [0]*M]

    E = [{} for _ in [0]*N]
    Eb = [{} for _ in [0]*N]
    for a,b,c in ABC:
        E[a-1][b-1] = -c
        Eb[b-1][a-1] = -c

    #0 -> N-1 経路上にない頂点を除く
    V1 = [False]*N
    V1[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        for j in E[i]:
            if V1[j]:continue
            qa(j)
            V1[j]=True
    V2 = [False]*N
    V2[-1] = True
    qa(N-1)
    while q:
        i = qp()
        for j in Eb[i]:
            if V2[j] or not V1[j]:continue
            qa(j)
            V2[j]=True
    for i in range(N):
        if V1[i] and V2[i]:continue
        for j in Eb[i]:
            E[j].pop(i)

    INFTY = 10**18
    d = [INFTY]*N
    d[0] = 0

    def update():
        done = [False]*N
        done[0] = True
        q = [0]
        qp = q.pop
        qa = q.append
        while q:
            i = qp()
            di = d[i]
            for j,c in list(E[i].items()):
                d[j] = min(d[j],d[i]+c)
                if not done[j]:
                    qa(j)
                    done[j] = True

    for _ in range(N-1):update()
    dc = d[:]
    update()
    if dc!=d:
        print("inf")
    else:
        print((-d[-1]))
main()
# Original solution
from collections import deque

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

edges = []
dfsEdges = [[] for _ in range(N)]
dfsReverseEdges = [[] for _ in range(N)]

for _ in range(M):
    back, to, cost = list(map(int, input().split()))
    back -= 1
    to -= 1
    edges.append((back, to, -cost))

    dfsEdges[back].append(to)
    dfsReverseEdges[to].append(back)

minDist = [float('inf') for _ in range(N)]
minDist[0] = 0

canGo = [False for _ in range(N)]
canBack = [False for _ in range(N)]

canGo[0] = True
canBack[N - 1] = True

def dfs(start, edge, confilm):
    que = deque([])
    que.append(start)

    while que:
        now = que.pop()
        for to in edge[now]:
            if not confilm[to]:
                que.append(to)
                confilm[to] = True

dfs(0, dfsEdges, canGo)
dfs(N - 1, dfsReverseEdges, canBack)

for time in range(N):
    for back, to, cost in edges:
        if minDist[to] > minDist[back] + cost:
            minDist[to] = minDist[back] + cost
            if time == N - 1:
                if canGo[to] and canBack[to]:
                    print('inf')
                    exit(0)

print((-minDist[N - 1]))

# Optimized solution
N, M = list(map(int, input().split()))
edges = []
E = [[] for _ in range(N)]

for _ in range(M):
    fr, to, cost = list(map(int, input().split()))
    fr -= 1
    to -= 1
    edges.append((fr, to, -cost))
    E[to].append(fr)

def canGo():
    st = [N - 1]
    visited = [False] * N
    visited[N - 1] = True
    while st:
        for to in E[st.pop()]:
            if visited[to]:
                continue
            visited[to] = True
            st.append(to)
    return visited

V = canGo()

minDist = [float('inf')] * N
minDist[0] = 0

for i in range(N + 1):
    for fr, to, cost in edges:
        d = minDist[fr] + cost
        if minDist[to] > d:
            if i == N and V[to]:
                print('inf')
                exit()
            minDist[to] = d

print((-minDist[N - 1]))
# Original solution
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
G = [[-float('inf')] * N for _ in range(N)]
score = [-float('inf')] * N
score[0] = 0
passed = [False] * N

for m in range(M):
    a, b, c = [int(x) for x in input().strip().split()]
    G[a-1][b-1] = c

updated = [False] * N
updated[0] = True
updated2 = False
for n in range(N):
    for i in range(1, N+1):
        if not updated[i-1]:
            continue
        updated[i-1] = False
        for j in range(1, N+1):
            # print('i={}, j={}'.format(i, j), end='')
            if i == j:
                # print(score)
                continue
            if G[i-1][j-1] != -float('inf') and score[j-1] < score[i-1] + G[i-1][j-1]:
                score[j-1] = score[i-1] + G[i-1][j-1]
                updated[j-1] = True
                if j == N-1:
                    updated2 = True
            else:
                if j == N-1:
                    updated2 = False
            # print(score)

if updated2:
    print('inf')
else:
    print((score[N-1]))

# Optimized solution
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
score = [-float('inf')] * N
score[0] = 0
passed = [False] * N
edges = [0] * M
for m in range(M):
    edges[m] = tuple([int(x) for x in input().strip().split()])

for n in range(N):
    updated = False
    for (i, j, c) in edges:
        # print('i={}, j={}'.format(i, j), end='')
        if score[j-1] < score[i-1] + c:
            score[j-1] = score[i-1] + c
            if j == N-1:
                updated = True
        # print(score)
    if not updated:
        break

if updated:
    print('inf')
else:
    print((score[N-1]))