AtCoder Beginner Contest 061 - Score Attack

There is a directed graph with N vertices and M edges.
The i-th edge (1≤i≤M) points from vertex a_i to vertex b_i, and has a weight c_i.
We will play the following single-player game using this graph and a piece.
Initially, the piece is placed at vertex 1, and the score of the player is set to 0.
The player can move the piece as follows:
 - When the piece is placed at vertex a_i, move the piece along the i-th edge to vertex b_i. After this move, the score of the player is increased by c_i.
The player can end the game only when the piece is placed at vertex N.
The given graph guarantees that it is possible to traverse from vertex 1 to vertex N.
When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf.

-----Constraints-----
 - 2≤N≤1000 
 - 1≤M≤min(N(N-1),2000) 
 - 1≤a_i,b_i≤N (1≤i≤M) 
 - a_i≠b_i (1≤i≤M) 
 - a_i≠a_j or b_i≠b_j (1≤i<j≤M) 
 - -10^9≤c_i≤10^9 (1≤i≤M)
 - c_i is an integer.
 - In the given graph, there exists a path from vertex 1 to vertex N.

-----Input-----
Input is given from Standard Input in the following format:  
N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

-----Output-----
Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf.  

-----Sample Input-----
3 3
1 2 4
2 3 3
1 3 5

-----Sample Output-----
7

There are two ways to move the piece to vertex N=3:
 - vertex 1 → vertex 2 → vertex 3 : score 4+3=7
 - vertex 1 → vertex 3 : score 5
Thus, the maximum possible score at the end of the game is 7.

Difficulty: MEDIUM

Starter code:

Solutions:
(N, M) = map(int, input().split())
edges = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	edges.append([a, b, c])
dist = [float('inf')] * (N + 1)
dist[1] = 0
for _ in range(N - 1):
	for (a, b, c) in edges:
		dist[b] = min(dist[b], dist[a] - c)
ans = dist[N]
for (a, b, c) in edges:
	dist[b] = min(dist[b], dist[a] - c)
if ans == dist[N]:
	print(-ans)
else:
	print('inf')


INF = 10 ** 30
import sys
sys.setrecursionlimit(10 ** 6)

def bellman_ford(s, t, g):
	d = [INF for _ in range(n)]
	d[s] = 0
	val_at_t = INF
	for i in range(n):
		for (x, y, z) in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
		if i == n - 1 and val_at_t > d[t]:
			return []
		val_at_t = d[t]
	return d
(n, m) = list(map(int, input().split()))
g = []
for _ in range(m):
	(x, y, z) = list(map(int, input().split()))
	x -= 1
	y -= 1
	z *= -1
	g.append([x, y, z])
ans = bellman_ford(0, n - 1, g)
print(-ans[n - 1] if ans else 'inf')


(N, M) = map(int, input().split())
ABC = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	c = -c
	ABC.append([a, b, c])

def BellmanFord():
	inf = float('Inf')
	dist = [inf for i in range(N)]
	dist[0] = 0
	for i in range(N):
		for edge in ABC:
			if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
				dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
				if i == N - 1 and edge[1] - 1 == N - 1:
					return inf
	return -dist[N - 1]
print(BellmanFord())


import queue

def bfs(G, s):
	st = set()
	q = queue.Queue()
	st.add(s)
	q.put(s)
	while not q.empty():
		p = q.get()
		for (v, _) in G[p]:
			if not v in st:
				st.add(v)
				q.put(v)
	return st

def solve(G, st):
	n = len(G)
	score = [-float('inf')] * n
	score[0] = 0
	for i in range(n):
		f = True
		for s in range(n):
			for (t, u) in G[s]:
				if not s in st or not t in st:
					continue
				if score[t] < score[s] + u:
					f = False
					score[t] = score[s] + u
		if f:
			break
		if i == n - 1:
			return 'inf'
	return score[n - 1]

def main():
	(n, m) = map(int, input().split())
	G = [[] for _ in range(n)]
	revG = [[] for _ in range(n)]
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		G[a].append([b, c])
		revG[b].append([a, c])
	st1 = bfs(G, 0)
	st2 = bfs(revG, n - 1)
	st = st1 & st2
	print(solve(G, st))

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
abc = []
for _ in range(M):
	abc.append(list(map(int, input().split())))
cost = [-float('inf')] * N
cost[0] = 0
for i in range(N):
	update = False
	for (a, b, c) in abc:
		(a, b) = (a - 1, b - 1)
		if cost[a] != -10 ** 10 * N:
			if cost[b] < cost[a] + c:
				cost[b] = cost[a] + c
				update = True
	if i == 0:
		Max = cost[N - 1]
	elif i < N - 1:
		Max = max(Max, cost[N - 1])
if update == True and Max < cost[N - 1]:
	print('inf')
else:
	print(Max)


(N, M) = map(int, input().split())
ABC = [tuple(map(int, input().split())) for i in range(M)]
INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(N):
	for (a, b, c) in ABC:
		(a, b, c) = (a - 1, b - 1, -c)
		if dist[b] > dist[a] + c:
			dist[b] = dist[a] + c
			if i == N - 1 and b == N - 1:
				print('inf')
				return
print(-dist[-1])


import sys
input = sys.stdin.buffer.readline
inf = 10 ** 18
(N, M) = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
negative = [False] * (N + 1)
cost = [inf] * (N + 1)
cost[1] = 0
for loop in range(N):
	update = False
	for (a, b, c) in ABC:
		if cost[b] > cost[a] - c:
			cost[b] = cost[a] - c
			if loop == N - 1:
				negative[b] = True
ans = -cost[N]
if negative[N]:
	ans = 'inf'
print(ans)


import sys
rl = sys.stdin.readline

def main():
	(n, m) = list(map(int, rl().strip().split()))
	eaw = [list(map(int, rl().strip().split())) for _ in range(m)]
	d = dict((((x[0] - 1, x[1] - 1), -x[2]) for x in eaw))
	inf = 10 ** 14
	mdl = [inf] * n
	mdl[0] = 0

	def blrelax(dl, k):
		for _ in range(k):
			for e in iter(d):
				if dl[e[0]] + d[e] < dl[e[1]]:
					dl[e[1]] = dl[e[0]] + d[e]
	blrelax(mdl, n - 1)
	a1 = mdl[n - 1]
	blrelax(mdl, n)
	a2 = mdl[n - 1]
	if a1 > a2:
		print('inf')
	else:
		print(-a1)

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())

def find_negative_loop(n, w, es):
	dist = [float('inf')] * n
	dist[1] = 0
	for i in range(n):
		for j in range(w):
			e = es[j]
			if dist[e[1]] > dist[e[0]] + e[2]:
				dist[e[1]] = dist[e[0]] + e[2]
				if i == n - 1:
					return True
	return False

def shortest_path(s, n, w, es):
	dist = [float('inf')] * n
	dist[s] = 0
	while True:
		update = False
		for (p, q, r) in es:
			if dist[p] != float('inf') and dist[q] > dist[p] + r:
				dist[q] = dist[p] + r
				update = True
		if not update:
			break
	return dist
graph = [[] for _ in range(N + 1)]
elist = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	graph[a].append(b)
	elist.append((a, b, -c))
visited = [None] * (N + 1)

def check_reachable(u):
	visited[u] = True
	if u == N:
		reachable[u] = True
		return True
	elif reachable[u] != None:
		return reachable[u]
	cnt = 0
	for v in graph[u]:
		if not visited[v]:
			ret = check_reachable(v)
			if ret:
				cnt += 1
	if cnt > 0:
		reachable[u] = True
		return True
	else:
		reachable[u] = False
		return False
reachable = [None] * (N + 1)
for i in range(1, N + 1):
	if reachable[i] == None:
		visited = [False] * (N + 1)
		check_reachable(i)
elist2 = []
for (a, b, nc) in elist:
	if reachable[b]:
		elist2.append((a, b, nc))
M2 = len(elist2)
res1 = find_negative_loop(N + 1, M2, elist2)
if res1:
	print('inf')
else:
	res2 = shortest_path(1, N + 1, M2, elist2)
	print(-res2[N])


def bellman_ford(V, E, s, std):
	dist = [float('inf') for _ in range(V)]
	dist[s] = 0
	for i in range(V):
		for (s, t, d) in std:
			s -= 1
			t -= 1
			d = -d
			if dist[t] > dist[s] + d:
				dist[t] = dist[s] + d
				if i == V - 1 and t + 1 == V:
					return -1
	return dist

def main():
	(N, M) = map(int, input().split())
	abc = [list(map(int, input().split())) for _ in range(M)]
	dist = bellman_ford(N, M, 0, abc)
	if dist == -1:
		print('inf')
		exit()
	else:
		print(-dist[N - 1])
main()


(n, m) = [int(i) for i in input().split()]
abc = []
for _ in range(m):
	(a, b, c) = [int(i) for i in input().split()]
	abc.append([a - 1, b - 1, c])
dist = [-10 ** 18] * n
dist[0] = 0

def update():
	global dist
	for (a, b, c) in abc:
		if dist[a] + c > dist[b]:
			dist[b] = dist[a] + c
for _ in range(n):
	update()
a = dist[-1]
for _ in range(n):
	update()
b = dist[-1]
if a != b:
	print('inf')
else:
	print(a)


from collections import deque

def belman(s, n, w, es):
	d = [-float('inf')] * n
	d[s] = 0
	c = 0
	while True:
		update = False
		for (p, q, r) in es:
			if d[p] != -float('inf') and d[q] < d[p] + r:
				d[q] = d[p] + r
				update = True
				c += 1
			if c > w:
				return 'inf'
		if not update:
			break
	return d[n - 1]

def use_path(n, start, es):
	q = deque()
	chk = [False] * n
	q.append(start)
	chk[start] = True
	used = {start}
	while len(q) > 0:
		node = q.popleft()
		for nex in es[node]:
			if not chk[nex]:
				chk[nex] = True
				q.append(nex)
				used.add(nex)
	return used
(n, w) = map(int, input().split())
es = []
l = [[] for i in range(n)]
r = [[] for i in range(n)]
for i in range(w):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	l[a].append(b)
	r[b].append(a)
	es.append((a, b, c))
use = use_path(n, 0, l) & use_path(n, n - 1, r)
ess = [(a, b, c) for (a, b, c) in es if a in use and b in use]
print(belman(0, n, w * 2, ess))


def main():
	(N, M) = map(int, input().split())
	g = [[] for _ in range(N + 1)]
	INF = -1 * 10 ** 9 * 1000
	d = [INF] * (N + 1)
	d[1] = 0
	for _ in range(M):
		(a, b, c) = map(int, input().split())
		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] != INF and d[x] + c > d[y]:
					d[y] = d[x] + c
					if y == N and i > N:
						print('inf')
						exit()
	print(d[-1])
main()


(N, M) = map(int, input().split())
egdes = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 13
dist = [INF] * (N + 1)
dist[1] = 0
for _ in range(N - 1):
	for (a, b, c) in egdes:
		dist[b] = min(dist[b], dist[a] - c)
ans = dist[N]
for (a, b, c) in egdes:
	dist[b] = min(dist[b], dist[a] - c)
print(-ans if ans == dist[N] else 'inf')


(N, M) = list(map(int, input().split(' ')))
INF = -10 ** 20
graph = [INF for _ in range(N + 1)]
edges = []
for _ in range(M):
	(a, b, c) = list(map(int, input().split(' ')))
	edges.append((a, b, c))
graph[1] = 0
for i in range(2 * N):
	for edge in edges:
		(fr, to, point) = edge
		if graph[fr] + point > graph[to] and graph[fr] != INF:
			graph[to] = graph[fr] + point
			if to == N and i > N:
				print('inf')
				exit()
print(graph[-1])


(N, M) = map(int, input().split())
dp = [-float('INF')] * (N + 1)
dp[1] = 0
edges = [list(map(int, input().split())) for _ in range(M)]
cnt = 0
while cnt < N:
	cnt += 1
	for (a, b, c) in edges:
		dp[b] = max(dp[a] + c, dp[b])
tmp = dp[N]
cnt = 0
while cnt < N:
	cnt += 1
	for (a, b, c) in edges:
		dp[b] = max(dp[a] + c, dp[b])
if dp[N] > tmp:
	print('inf')
else:
	print(dp[N])


import sys
INF = float('inf')

def Bellmanford(n, edges, 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 -1 * d[n - 1]
(N, M) = list(map(int, sys.stdin.readline().split()))
Edges = [0] * M
for i in range(M):
	(a, b, c) = list(map(int, sys.stdin.readline().split()))
	Edges[i] = (a - 1, b - 1, -c)
ans = Bellmanford(N, Edges, 0)
print(ans)


(n, m) = [int(i) for i in input().split()]
es = [[int(j) for j in input().split()] for i in range(m)]
x = [float('-inf')] * (n + 1)
x[1] = 0
for i in range(n):
	for (a, b, c) in es:
		x[b] = max(x[b], x[a] + c)
prevxn = x[n]
for (a, b, c) in es:
	x[b] = max(x[b], x[a] + c)
if prevxn != x[n]:
	print('inf')
else:
	print(x[n])


import math
INF = float('inf')
(V, E) = map(int, input().split())
es = []
for _ in range(E):
	(a, b, c) = map(int, input().split())
	es.append([a - 1, b - 1, -c])
d = [INF] * V
d[0] = 0
cnt = [0] * V
for _ in range(V):
	updated = False
	for e in es:
		if math.isinf(d[e[0]]):
			continue
		if d[e[1]] > d[e[0]] + e[2]:
			d[e[1]] = d[e[0]] + e[2]
			cnt[e[1]] += 1
			updated = True
	if not updated:
		break
print(-d[V - 1] if cnt[V - 1] < V else 'inf')


INF = float('inf')

def Bellmanford(n, edges):
	dp = [INF] * n
	dp[0] = 0
	for i in range(n):
		for (u, v, c) in edges:
			if dp[u] != INF and dp[u] + c < dp[v]:
				dp[v] = dp[u] + c
				if i == n - 1 and v == n - 1:
					return 'inf'
	return -dp[n - 1]
(N, M) = map(int, input().split())
E = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	E.append((a - 1, b - 1, -c))
ans = Bellmanford(N, E)
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

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

def main():
	pass

def __starting_point():
	main()

def bellman_ford(edges, N, start, goal):
	dist = [float('inf') for _ in range(N)]
	dist[start] = 0
	for i in range(N * 2):
		for (fro, to, cost) in edges:
			if dist[to] > dist[fro] + cost:
				dist[to] = dist[fro] + cost
				if i == N - 1:
					dist[to] = -float('inf')
	return -dist[goal]
(N, M) = list(map(int, input().split()))
edges = []
for _ in range(M):
	(a, b, c) = list(map(int, input().split()))
	edges.append((a - 1, b - 1, -c))
cost = [float('inf') for _ in range(N)]
start = 0
goal = N - 1
ans = bellman_ford(edges, N, start, goal)
if ans == float('inf'):
	print(ans)
else:
	print(ans)
__starting_point()


(n, m) = map(int, input().split())
edge = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edge.append((a, b, -c))
dis = [float('inf')] * (n + 1)
dis[1] = 0
f = 0
for i in range(n):
	for (a, b, c) in edge:
		if dis[b] > dis[a] + c:
			dis[b] = dis[a] + c
			if i == n - 1:
				f = 1
ans = dis[n]
if f:
	for _ in range(n):
		for (a, b, c) in edge:
			if dis[b] > dis[a] + c:
				dis[b] = dis[a] + c
				if b == n:
					print('inf')
					exit(0)
print(-ans)


(N, M) = map(int, input().split())
abc = [[int(x) for x in input().split()] for _ in range(M)]
Edges = [None] * M
for i in range(M):
	Edges[i] = (abc[i][0] - 1, abc[i][1] - 1, -abc[i][2])

def bellman_ford(N, edges, s):
	dist = [float('inf')] * N
	dist[s] = 0
	for n in range(N):
		for (u, v, c) in edges:
			if dist[u] != float('inf') and dist[v] > dist[u] + c:
				dist[v] = dist[u] + c
				if n == N - 1 and v == N - 1:
					return 'inf'
	return -dist[-1]
print(bellman_ford(N, Edges, 0))


INF = float('inf')

def solve():
	lp = [-INF] * n
	lp[0] = 0
	for i in range(n):
		for (a, b, c) in es:
			if lp[a] != -INF and lp[b] < lp[a] + c:
				lp[b] = lp[a] + c
				if i == n - 1 and b == n - 1:
					return 'inf'
	return lp[n - 1]
(n, m) = map(int, input().split())
es = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	es.append((a, b, c))
print(solve())


(N, M) = map(int, input().split())
edges = []
for m in range(M):
	(a, b, c) = map(int, input().split())
	edges.append([a - 1, b - 1, -c])
inf = float('inf')
dist = [inf for i in range(N)]
dist[0] = 0
dist_n = [inf for i in range(N)]
negative = [-1 for i in range(N)]
for i in range(N - 1):
	for e in edges:
		if dist[e[1]] > dist[e[0]] + e[2]:
			dist[e[1]] = dist[e[0]] + e[2]
for i in range(N):
	for e in edges:
		if negative[e[0]] > 0:
			negative[e[1]] = 1
		if dist[e[1]] > dist[e[0]] + e[2]:
			dist[e[1]] = dist[e[0]] + e[2]
			negative[e[1]] = 1
if negative[N - 1] > 0:
	print(inf)
else:
	print(-dist[N - 1])


import sys
input = sys.stdin.readline

def bellmanford(G, s):
	n = len(G)
	inf = -float('inf')
	dist = [inf] * n
	dist[s] = 0
	for i in range(n):
		for v in range(n):
			for (w, c) in G[v]:
				if dist[w] < dist[v] + c:
					dist[w] = dist[v] + c
					if i >= n - 1 and w == n - 1:
						return -1
	return dist

def main():
	(N, M) = map(int, input().split())
	graph = [[] for _ in range(N)]
	for _ in range(M):
		(a, b, c) = map(int, input().split())
		a -= 1
		b -= 1
		graph[a].append((b, c))
	dist = bellmanford(graph, 0)
	if dist == -1:
		print('inf')
	else:
		print(dist[N - 1])

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
abc = [tuple(map(int, input().split())) for i in range(m)]
es = []
for (a, b, c) in abc:
	(a, b) = (a - 1, b - 1)
	es.append((a, b, c))
INF = float('inf')

def find_negative_loop(n, es, s):
	dist = [-INF] * n
	dist[s] = 0
	for i in range(n):
		for (a, b, c) in es:
			if dist[b] < dist[a] + c:
				dist[b] = dist[a] + c
				if i == n - 1 and b == n - 1:
					return INF
	return dist[n - 1]
ans = find_negative_loop(n, es, 0)
if ans == INF:
	print('inf')
	return
print(ans)


(n, m) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]

def bellman_ford(s, g):
	dist = [float('inf')] * n
	dist[s] = 0
	negative = [False] * n
	for i in range(2 * n):
		for (a, b, c) in abc:
			a -= 1
			b -= 1
			c = -c
			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					negative[b] = True
	if negative[g]:
		ret = 'inf'
	else:
		ret = -dist[g]
	return ret
ans = bellman_ford(0, n - 1)
print(ans)


(n, m) = map(int, input().split())
NINF = -10 ** 20
edge = []
dist = [NINF] * n
dist[0] = 0
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edge.append((a - 1, b - 1, c))
for i in range(n):
	for (a, b, c) in edge:
		if dist[a] != NINF and dist[b] < dist[a] + c:
			dist[b] = dist[a] + c
			if i == n - 1 and b == n - 1:
				print('inf')
				exit()
print(dist[-1])


def bellmanford(s, n, es):
	d = [float('inf')] * n
	neg = [False] * n
	d[s] = 0
	for i in range(n):
		for (p, q, r) in es:
			if d[p] != float('inf') and d[q] > d[p] + r:
				d[q] = d[p] + r
				if i == n - 1:
					neg[q] = True
	return (d, neg)
(n, w) = map(int, input().split())
es = []
for _ in range(w):
	(x, y, z) = map(int, input().split())
	es.append([x - 1, y - 1, -z])
(d, neg) = bellmanford(0, n, es)
if neg[-1]:
	print('inf')
else:
	print(-d[-1])


(N, M) = map(int, input().split())
INF = 10 ** 13
edge = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	edge.append((a, b, -c))
dist = [INF for i in range(N)]
dist[0] = 0
neg_cycle = False
for i in range(N + 1):
	update = False
	N_update = False
	for (a, b, c) in edge:
		if dist[a] == INF:
			continue
		if dist[a] + c < dist[b]:
			dist[b] = dist[a] + c
			update = True
			if b == N - 1:
				N_update = True
	if not update:
		break
	if i >= N - 1 and N_update:
		neg_cycle = True
if neg_cycle:
	print('inf')
else:
	print(-dist[N - 1])


(N, M) = map(int, input().split())
es = [None] * M
for i in range(M):
	(a, b, c) = map(int, input().split())
	es[i] = (a, b, c)
INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(N):
	for (f, t, c) in es:
		(f, t) = (f - 1, t - 1)
		c = c * -1
		if d[f] != INF and d[t] > d[f] + c:
			d[t] = d[f] + c
			if i == N - 1 and t == N - 1:
				print('inf')
				exit()
print(-d[-1])


INF = float('inf')

def bellman_ford(edges, n, s):
	d = [0] + [INF] * (n - 1)
	for i in range(n):
		for (f, t, c) in edges:
			if d[f] == INF:
				continue
			if d[t] > d[f] + c:
				if i == n - 1:
					d[t] = -INF
				else:
					d[t] = d[f] + c
	for i in range(n):
		for (f, t, c) in edges:
			if d[f] == INF:
				continue
			d[t] = min(d[t], d[f] + c)
	return d
(n, m) = map(int, input().split())
es = [None] * m
for i in range(m):
	(f, t, c) = map(int, input().split())
	es[i] = (f - 1, t - 1, -c)
d = bellman_ford(es, n, 0)
print(-d[n - 1])


(N, M) = map(int, input().split())
side = [[] for _ in range(N)]
for _ in range(M):
	(a, b, c) = map(int, input().split())
	side[a - 1].append([b - 1, c])
node = [-float('inf')] * N
node[0] = 0
for _ in range(N):
	for i in range(N):
		for (b, c) in side[i]:
			node[b] = max(node[b], node[i] + c)
for _ in range(N):
	for i in range(N):
		for (b, c) in side[i]:
			if node[b] < node[i] + c:
				node[b] = float('inf')
print(node[-1])


def reachable(es, source):
	ret = {source}
	Q = [source]
	while Q:
		cur = Q.pop()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def BellmanFord(V: int, es: list, source=0):
	INF = float('inf')
	D = [INF] * V
	D[source] = 0
	for _ in range(V):
		upd = False
		for (f, t, c) in es:
			tmp = D[f] + c
			if D[t] > tmp:
				D[t] = tmp
				upd = True
		if not upd:
			return D[-1]
	else:
		return None

def main():
	(N, M, *L) = map(int, open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	tmp = []
	for (a, b, c) in zip(*[iter(L)] * 3):
		fwd[a - 1].append(b - 1)
		bwd[b - 1].append(a - 1)
		tmp += [(a - 1, b - 1, -c)]
	ra = reachable(fwd, 0) & reachable(bwd, N - 1)
	ans = BellmanFord(N, [(a, b, c) for (a, b, c) in tmp if a in ra and b in ra])
	if ans == None:
		print('inf')
	else:
		print(-ans)

def __starting_point():
	main()
__starting_point()


import io
(nim, mike) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in [0] * mike]
g = [[] for _ in [0] * nim]
[g[a - 1].append([b - 1, c]) for (a, b, c) in abc]
dist = [-10 ** 15 for _ in [0] * nim]
dist[0] = 0
(a, b) = (-10 ** 15, -10 ** 15)
for _ in range(nim):
	for p in range(nim):
		for (i, j) in g[p]:
			dist[i] = max(dist[i], dist[p] + j)
	(a, b) = (b, dist[nim - 1])
if a == b:
	print(a)
else:
	print('inf')


import sys
(N, M) = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]
INF = 1 << 60
cost = [-INF] * (N + 1)
cost[1] = 0
for i in range(N):
	for (n, nn, c) in edge:
		if cost[nn] < cost[n] + c:
			if i == N - 1 and nn == N:
				print('inf')
				sys.exit()
			cost[nn] = cost[n] + c
print(cost[N])


import sys
(N, M) = map(int, input().split())
edge = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	edge.append([a - 1, b - 1, -c])
inf = 10 ** 30
dist = [inf] * N
dist[0] = 0
for i in range(N):
	for (x, y, z) in edge:
		if dist[y] <= dist[x] + z:
			continue
		dist[y] = dist[x] + z
ans = dist[N - 1]
visit = [False] * N
for i in range(N):
	for (x, y, z) in edge:
		if visit[x]:
			visit[y] = True
		if dist[y] <= dist[x] + z:
			continue
		visit[y] = True
		dist[y] = dist[x] + z
if visit[N - 1]:
	print('inf')
else:
	print(-ans)


(n, m) = list(map(int, input().split()))
a = [0] * m
b = [0] * m
c = [0] * m
INF = float('inf')
dist = [INF] * n
dist[0] = 0
for i in range(m):
	(a[i], b[i], c[i]) = list(map(int, input().split()))
	a[i] -= 1
	b[i] -= 1
	c[i] *= -1
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[n - 1]
neg = [False] * n
for loop in range(n):
	for i in range(m):
		if dist[b[i]] > dist[a[i]] + c[i]:
			dist[b[i]] = dist[a[i]] + c[i]
			neg[b[i]] = True
		if neg[a[i]]:
			neg[b[i]] = True
if neg[n - 1]:
	print('inf')
else:
	print(-ans)


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
(N, M) = map(int, input().split())
edge = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	edge.append((a, b, -c))
inf = 10 ** 18
score = [inf] * (N + 1)
score[1] = 0
for _ in range(N - 1):
	for (a, b, c) in edge:
		score[b] = min(score[b], score[a] + c)
goal = score[N]
for (a, b, c) in edge:
	score[b] = min(score[b], score[a] + c)
if goal != score[N]:
	print('inf')
else:
	print(-goal)


(N, M) = list(map(int, input().split()))
abc = []
for _ in range(M):
	abc.append(list(map(int, input().split())))
cost = [-float('inf')] * N
cost[0] = 0
for i in range(2):
	for (a, b, c) in abc:
		(a, b) = (a - 1, b - 1)
		cost[b] = max(cost[b], cost[a] + c)
	if i == 0:
		ans = cost[N - 1]
	else:
		Max = cost[N - 1]
if ans != Max:
	print('inf')
else:
	print(ans)


(n, m) = map(int, input().split())
a = []
b = []
c = []
for _ in range(m):
	INPUT = list(map(int, input().split()))
	a.append(INPUT[0])
	b.append(INPUT[1])
	c.append(-INPUT[2])
dist = [float('inf') for _ in range(n)]
dist[0] = 0
for _ in range(1, n):
	for j in range(m):
		if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
			dist[b[j] - 1] = dist[a[j] - 1] + c[j]
ans = dist[n - 1]
for j in range(m):
	if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
		dist[b[j] - 1] = dist[a[j] - 1] + c[j]
if dist[n - 1] < ans:
	print('inf')
else:
	print(-ans)


ai = lambda : list(map(int, input().split()))
(n, m) = ai()
from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
	(a, b, c) = ai()
	edge[a - 1].append([b - 1, -c])
dist = [float('inf')] * n
dist[0] = 0
vs = {0}
i = 0
while vs:
	cur_v = vs.pop()
	for (v, c) in edge[cur_v]:
		if dist[v] > dist[cur_v] + c:
			dist[v] = dist[cur_v] + c
			vs.add(v)
			if i >= n - 1 and v == n - 1:
				print('inf')
				exit()
	i += 1
	if i > n * 2:
		break
print(-dist[-1])


(N, M) = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
	(A[i], B[i], C[i]) = map(int, input().split())
	A[i] -= 1
	B[i] -= 1
inf = 123456789123456789123456789
dist = [-inf] * N
dist[0] = 0
bounded = True
for i in range(max(2 * N - 3, 4)):
	for j in range(M):
		if dist[B[j]] < dist[A[j]] + C[j]:
			dist[B[j]] = dist[A[j]] + C[j]
			if B[j] == N - 1 and i >= N:
				bounded = False
if not bounded:
	print('inf')
else:
	print(dist[N - 1])


import sys
(N, M) = map(int, input().split())
graph = [0] * M
for m in range(M):
	(a, b, c) = map(int, input().split())
	graph[m] = (a, b, -c)
INF = 1e+18
distance = [INF] * N
distance[0] = 0
for n in range(N):
	for i in range(M):
		(a, b, c) = graph[i]
		if INF != distance[a - 1] and distance[b - 1] > distance[a - 1] + c:
			distance[b - 1] = distance[a - 1] + c
			if b == N and n == N - 1:
				print('inf')
				sys.exit()
print(-distance[N - 1])


(N, M) = [int(n) for n in input().split()]
edges = []
for m in range(M):
	(a, b, c) = [int(w) for w in input().split()]
	a -= 1
	b -= 1
	edges.append((a, b, c * -1))
inf = 10000000000000000
dist = [inf] * N
dist[0] = 0
for i in range(N - 1):
	for (a, b, c) in edges:
		dist[b] = min(dist[b], dist[a] + c)
ans = dist[N - 1]
negative = [inf] * N
negative[0] = 0
for i in range(N):
	for (a, b, c) in edges:
		negative[b] = min(negative[b], negative[a] + c)
if negative[N - 1] < dist[N - 1]:
	print('inf')
else:
	print(-1 * dist[N - 1])


def bellman_ford(s):
	d = [float('inf')] * n
	d[s] = 0
	for i in range(n):
		e = 0
		for (x, y, z) in g:
			if d[y] > d[x] + z and d[x] != float('inf'):
				d[y] = d[x] + z
				e += 1
				if i == n - 1 and y == n - 1:
					return 'inf'
	return -1 * d[n - 1]
(n, m) = map(int, input().split())
g = []
for k in range(m):
	(a, b, c) = map(int, input().split())
	g.append([a - 1, b - 1, -c])
print(bellman_ford(0))


import sys
(n, m) = map(int, input().split())
edges = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	edges.append((a, b, c))
score = [-10 ** 50] * n
score[0] = 0
for i in range(n):
	for (a, b, c) in edges:
		if score[b] < score[a] + c:
			score[b] = score[a] + c
res = score[n - 1]
for i in range(n):
	for (a, b, c) in edges:
		if score[b] < score[a] + c:
			score[b] = score[a] + c
if res < score[n - 1]:
	res = 'inf'
print(res)


(N, M) = map(int, input().split())
es = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	c *= -1
	es.append((a, b, c))
INF = float('inf')

def solve():
	d = [INF for i in range(N)]
	d[0] = 0
	for i in range(N):
		for (fr, to, cost) in es:
			if d[fr] == INF:
				continue
			if d[to] > d[fr] + cost:
				d[to] = d[fr] + cost
				if i == N - 1 and to == N - 1:
					return 'inf'
	return -d[N - 1]
print(solve())


INF = -float('inf')

def bellmanford(n, e, r):
	costs = [INF] * n
	costs[r] = 0
	for i in range(n):
		for (u, v, c) in e:
			if costs[u] + c > costs[v] and costs[u] != INF:
				costs[v] = costs[u] + c
				if i == n - 1 and v == n - 1:
					return 'inf'
	return costs[n - 1]
(n, m) = map(int, input().split())
edge = []
for i in range(m):
	(a, b, t) = map(int, input().split())
	edge.append((a - 1, b - 1, t))
print(bellmanford(n, edge, 0))


(N, M) = list(map(int, input().split()))
from collections import deque
ls = [deque([]) for _ in range(N)]
for i in range(M):
	(a, b, c) = list(map(int, input().split()))
	(a, b) = (a - 1, b - 1)
	ls[a].append([b, c])
cost = [-10 ** 10 * N] * N
cost[0] = 0
for i in range(N):
	update = False
	q = [deque((m for m in l)) for l in ls]
	for j in range(N):
		if cost[j] != -10 ** 10 * N:
			while q[j]:
				(b, c) = q[j].pop()
				if cost[b] < cost[j] + c:
					cost[b] = cost[j] + c
					update = True
	if i == 0:
		Max = cost[N - 1]
	elif i < N - 1:
		Max = max(Max, cost[N - 1])
if update == True and Max < cost[N - 1]:
	print('inf')
else:
	print(Max)


INF = float('inf')

def Bellmanford(n, e, s):
	d = [INF] * n
	d[s] = 0
	for i in range(n):
		for (e_from, e_to, e_cost) in e:
			if d[e_from] != INF and d[e_to] > d[e_from] + e_cost:
				d[e_to] = d[e_from] + e_cost
				if i == n - 1 and e_to == n - 1:
					return 'inf'
	return -d[n - 1]
(n, m) = (int(x) for x in input().split())
edges = [None] * m
for i in range(m):
	(ai, bi, ci) = map(int, input().split())
	edges[i] = (ai - 1, bi - 1, -ci)
ans = Bellmanford(n, edges, 0)
print(ans)


inf = float('inf')
(n, m) = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(m)]
abc = [[ai[0] - 1, ai[1] - 1, -ai[2]] for ai in abc]
d = [inf] * n
d[0] = 0
for i in range(n):
	flag = False
	for abci in abc:
		if d[abci[1]] > d[abci[0]] + abci[2]:
			flag = True
			d[abci[1]] = d[abci[0]] + abci[2]
			if i == n - 1 and abci[1] == n - 1:
				print('inf')
				exit()
print(-d[n - 1])


from copy import deepcopy
(n, m) = [int(i) for i in input().split()]
es = [[int(j) for j in input().split()] for i in range(m)]
x = [float('-inf')] * (n + 1)
x[1] = 0
for i in range(n):
	for (a, b, c) in es:
		x[b] = max(x[b], x[a] + c)
xcp = [i for i in x]
prevxn = x[n]
for (a, b, c) in es:
	x[b] = max(x[b], x[a] + c)
if prevxn != x[n]:
	print('inf')
else:
	print(x[n])


(N, M) = map(int, input().split())
edges = [None] * M
INF = 10 ** 18
for i in range(M):
	(a, b, c) = map(int, input().split())
	edges[i] = (a - 1, b - 1, -c)

def bellman(n, edges, 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[-1]
ans = bellman(N, edges, 0)
print(ans)


import sys
(N, M) = map(int, input().split())
edge = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	edge.append([a - 1, b - 1, -c])
inf = 10 ** 30
dist = [inf] * N
dist[0] = 0
for i in range(N + 1):
	for (x, y, z) in edge:
		if dist[y] <= dist[x] + z:
			continue
		dist[y] = dist[x] + z
		if i == N and y == N - 1:
			print('inf')
			sys.exit()
print(-dist[N - 1])


def main():
	INF = float('inf')
	(N, M, *ABC) = map(int, open(0).read().split())
	D = [INF, 0] + [INF] * (N - 1)
	E = tuple(zip(*[iter(ABC)] * 3))
	for (a, b, c) in E:
		D[b] = min(D[b], D[a] - c)
	ans = D[-1]
	for (a, b, c) in E:
		D[b] = min(D[b], D[a] - c)
	print('inf' if ans != D[-1] else -ans)
main()


(n, m) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]
abc = [[a - 1, b - 1, -c] for (a, b, c) in abc]

def BellmanFord(edges, num_v, source):
	inf = float('inf')
	dist = [inf for i in range(num_v)]
	dist[source] = 0
	for i in range(num_v):
		for edge in edges:
			if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
				dist[edge[1]] = dist[edge[0]] + edge[2]
	negative = [False] * n
	for i in range(num_v):
		for edge in edges:
			if negative[edge[0]]:
				negative[edge[1]] = True
			if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
				negative[edge[1]] = True
	return (dist[n - 1], negative[n - 1])
(c, d) = BellmanFord(abc, n, 0)
if d:
	print('inf')
else:
	print(-c)


(n, m) = map(int, input().split())
abc = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	abc.append([a - 1, b - 1, -c])
abc.sort()
INF = 10 ** 18
d = [INF] * n
chk = [False] * n
d[0] = 0
for i in range(n - 1):
	for (a, b, c) in abc:
		if d[b] > d[a] + c:
			d[b] = d[a] + c
for i in range(n):
	for (a, b, c) in abc:
		if d[b] > d[a] + c:
			d[b] = d[a] + c
			chk[b] = True
			chk[a] = True
if chk[n - 1] == True:
	print('inf')
else:
	print(-d[n - 1])


def bellman(s, n, es):
	INF = float('inf')
	d = [INF] * n
	d[s] = 0
	for _ in range(n - 1):
		for (p, q, r) in es:
			if d[p] != INF and d[q] > d[p] + r:
				d[q] = d[p] + r
	for _ in range(n - 1):
		for (p, q, r) in es:
			if d[q] > d[p] + r:
				d[q] = -INF
	return d
(n, m) = map(int, input().split())
g = []
for _ in range(m):
	(vi, vj, w) = map(int, input().split())
	g.append([vi - 1, vj - 1, -w])
print(-bellman(0, n, g)[-1])


(n, m) = map(int, input().split())
data = []
for i in range(0, m):
	(a, b, c) = map(int, input().split())
	data.append((a, b, -c))
g = [float('inf') for _ in range(0, n + 1)]
g[1] = 0
negative = ['false' for _ in range(0, n + 1)]
for i in range(0, n):
	for j in range(0, m):
		(a, b, c) = data[j]
		if g[a] != float('inf') and g[b] > g[a] + c:
			g[b] = g[a] + c
			if i == n - 1:
				negative[b] = 'true'
if negative[n] == 'false':
	print(-g[n])
else:
	print('inf')


(n, m) = map(int, input().split())
es = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	es.append((a - 1, b - 1, -c))

def bellman_ford(s, v, e, es):
	d = [float('inf')] * v
	d[s] = 0
	for i in range(n):
		for (p, q, r) in es:
			if d[p] != float('inf') and d[q] > d[p] + r:
				d[q] = d[p] + r
				if i == n - 1 and q == n - 1:
					print('inf')
					exit()
	return d
d = bellman_ford(0, n, m, es)
print(-d[n - 1])


(n, m) = map(int, input().split())
INF = float('inf')
G = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	G.append([a - 1, b - 1, -c])

def main():
	D = [INF for _ in range(n)]
	D[0] = 0
	for i in range(n):
		for (x, y, z) in G:
			if D[x] != INF and D[y] > D[x] + z:
				D[y] = D[x] + z
				if i == n - 1 and y == n - 1:
					return 'inf'
	return -D[n - 1]
print(main())


import sys
sys.stdin.readline

def main():
	(N, M) = map(int, input().split())
	ABC = [tuple(map(int, input().split())) for _ in range(M)]
	INF = float('inf')
	cost = [-INF] * N
	cost[0] = 0
	for i in range(N - 1):
		for (a, b, c) in ABC:
			cost[b - 1] = max(cost[b - 1], cost[a - 1] + c)
	prev = cost[N - 1]
	for (a, b, c) in ABC:
		cost[b - 1] = max(cost[b - 1], cost[a - 1] + c)
	print(cost[N - 1] if cost[N - 1] == prev else 'inf')
main()


(n, m) = map(int, input().split())
(a, b) = ([list(map(int, input().split())) for i in range(m)], [float('INF')] * (n + 1))
b[1] = 0
for i in range(1, n + 1):
	for (s, t, u) in a:
		if b[t] > b[s] - u:
			b[t] = b[s] - u
			if i == n and t == n:
				print('inf')
				exit()
print(-b[-1])


import sys
(N, M) = map(int, input().split())
a = []
b = []
c = []
for m in range(0, M):
	(A, B, C) = map(int, input().split())
	a += [A]
	b += [B]
	c += [C]
V = [0] + [-10 ** 12] * (N - 1)
for n in range(N - 1):
	for m in range(M):
		u = a[m]
		v = b[m]
		if V[b[m] - 1] < V[a[m] - 1] + c[m]:
			V[b[m] - 1] = V[a[m] - 1] + c[m]
moji2 = [0] * N
for n in range(N):
	for m in range(M):
		u = a[m]
		v = b[m]
		if V[b[m] - 1] < V[a[m] - 1] + c[m]:
			V[b[m] - 1] = V[a[m] - 1] + c[m]
			moji2[b[m] - 1] = 1
			if moji2[N - 1]:
				print('inf')
				sys.exit()
print(V[N - 1])


(N, M) = list(map(int, input().split()))
sides = []
for i in range(M):
	sides.append(list(map(int, input().split())))
costs = [-10 ** 20] * N
costs[0] = 0
epoch = 0
update_number = 1
L = 0
while update_number > 0 and epoch < 2 * (N - 1):
	update_number = 0
	for side in sides:
		if costs[side[1] - 1] < costs[side[0] - 1] + side[2]:
			costs[side[1] - 1] = costs[side[0] - 1] + side[2]
			update_number += 1
	epoch += 1
	if epoch == N - 1:
		L = costs[N - 1]
if epoch == 2 * (N - 1) and L != costs[N - 1]:
	print('inf')
else:
	print(costs[N - 1])


(n, m) = map(int, input().split())
edges = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	edges.append((a, b, -c))
dist = [float('inf')] * n
dist[0] = 0
for i in range(n - 1):
	for (st, en, score) in edges:
		if dist[st] == float('inf'):
			continue
		if dist[en] > dist[st] + score:
			dist[en] = dist[st] + score
negative = [False] * n
for loop in range(n):
	for e in edges:
		(st, en, score) = e
		if dist[st] == float('inf'):
			continue
		if dist[en] > dist[st] + score:
			dist[en] = dist[st] + score
			negative[en] = True
		if negative[st]:
			negative[en] = True
if negative[n - 1]:
	print('inf')
else:
	print(-dist[n - 1])


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

def main():
	INF = 10 ** 18
	LI = lambda : [int(x) for x in sys.stdin.readline().split()]
	(N, M) = LI()
	root = []
	for _ in range(M):
		(a, b, c) = LI()
		root.append((a - 1, b - 1, c))
	node = [-INF] * N
	node[0] = 0
	up = False
	for _ in range(N):
		up = False
		for (a, b, c) in root:
			if node[a] + c > node[b]:
				node[b] = node[a] + c
				if b == N - 1:
					up = True
	if up:
		print('inf')
	else:
		print(node[N - 1])
main()


(n, m) = map(int, input().split())
edges = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	edges.append([a - 1, b - 1, -c])
inf = float('inf')
dist = [inf for i in range(n)]
dist[0] = 0
flag = False
for i in range(2 * n):
	for edge in edges:
		if edge[0] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
			dist[edge[1]] = dist[edge[0]] + edge[2]
			if i >= n - 1 and edge[1] == n - 1:
				flag = True
				break
if flag:
	print('inf')
else:
	print(-dist[n - 1])


(n, m) = map(int, input().split())
g = sorted([list(map(int, input().split())) for _ in range(m)])

def BellmanFord(edges, num_v, source):
	inf = float('inf')
	dist = [inf for i in range(num_v)]
	dist[source - 1] = 0
	for i in range(num_v):
		for edge in edges:
			if edge[0] != inf and dist[edge[1] - 1] > dist[edge[0] - 1] - edge[2]:
				dist[edge[1] - 1] = dist[edge[0] - 1] - edge[2]
				if i == num_v - 1 and edge[0] == num_v - 1:
					return -1
	return dist
if BellmanFord(g, n, 1) == -1:
	print('inf')
else:
	print(-BellmanFord(g, n, 1)[-1])


(n, m) = map(int, input().split())
ainf = -334334334334334334334334
es = []

def bf():
	d = [ainf] * n
	d[0] = 0
	i = 0
	sa = 0
	ta = 0
	for i in range(n + 1):
		for (p, q, r) in es:
			if d[p] != ainf and d[q] < d[p] + r:
				d[q] = d[p] + r
				if i == n - 1:
					sa = d[n - 1]
				if i == n:
					ta = d[n - 1]
	return (sa, ta, d[n - 1])
for _ in range(m):
	(x, y, z) = map(int, input().split())
	es.append([x - 1, y - 1, z])
(s, t, u) = bf()
if s == t:
	print(u)
else:
	print('inf')


import sys
input = sys.stdin.readline
INF = float('inf')

def Bellmanford(n, edges, 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, input().split())
edges = [None] * m
for i in range(m):
	(ai, bi, ci) = map(int, input().split())
	edges[i] = (ai - 1, bi - 1, -ci)
ans = Bellmanford(n, edges, 0)
print(ans)


def main():
	(N, M) = map(int, input().split())
	edges = []
	for _ in range(M):
		(a, b, c) = map(int, input().split())
		a -= 1
		b -= 1
		edges.append([a, b, c])
	d = [float('inf')] * N
	d[0] = 0
	for i in range(N - 1):
		for edge in edges:
			d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])
	ans = d[N - 1]
	for edge in edges:
		d[edge[1]] = min(d[edge[1]], d[edge[0]] - edge[2])
	if ans == d[N - 1]:
		print(-ans)
	else:
		print('inf')
main()


(n, m) = map(int, input().split())
e = [list(map(int, input().split())) for _ in range(m)]
inf = float('inf')
d = [inf] * (n + 1)
d[1] = 0
for _ in range(n):
	for (a, b, c) in e:
		d[b] = min(d[b], d[a] - c)
x = d[n]
for (a, b, c) in e:
	d[b] = min(d[b], d[a] - c)
if x != d[n]:
	print(inf)
else:
	print(-x)


import sys
S = sys.stdin.readlines()
(N, M) = map(int, S[0].split())
G = []
(a, b, c) = (0, 0, 0)
for i in range(M):
	(a, b, c) = map(int, S[i + 1].split())
	G.append((a - 1, b - 1, -c))
INF = 10 ** 15
D = [INF] * N
D[0] = 0
e = 0
for i in range(N - 1):
	for j in range(M):
		e = G[j]
		if D[e[0]] != INF and D[e[1]] > D[e[0]] + e[2]:
			D[e[1]] = D[e[0]] + e[2]
X = D[N - 1]
for j in range(M):
	e = G[j]
	if D[e[0]] != INF and D[e[1]] > D[e[0]] + e[2]:
		D[e[1]] = D[e[0]] + e[2]
if X == D[N - 1]:
	print(-X)
else:
	print('inf')


((n, m), *l) = [list(map(int, s.split())) for s in open(0)]
d = [0] * 2 + [9e+99] * n
for i in range(n * 2):
	for (a, b, c) in l:
		if d[b] > d[a] - c:
			d[b] = [d[a] - c, -9e+99][i > n]
	if i == n:
		x = d[n]
print([-x, 'inf'][d[n] != x])


(n, m) = map(int, input().split())
e = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	e.append((a - 1, b - 1, c))
maxdis = [-float('inf') for i in range(n)]
maxdis[0] = 0
mugen = False
for i in range(n):
	for j in e:
		(st, gl, cost) = j
		if maxdis[gl] < maxdis[st] + cost:
			maxdis[gl] = maxdis[st] + cost
			if i >= n - 1 and gl == n - 1:
				mugen = True
				break
if mugen:
	print('inf')
else:
	print(maxdis[n - 1])


(n, m) = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(m)]
node = [-float('inf') for i in range(n + 1)]
node[1] = 0
inf = False
for i in range(2 * n + 1):
	change = False
	for (s, e, c) in edge:
		if node[e] < node[s] + c:
			node[e] = node[s] + c
			if e == n:
				change = True
	if i >= n and change:
		inf = True
if inf:
	print('inf')
else:
	print(node[-1])


class BellmanFord:

	def __init__(self, s, V):
		self.graph = {}
		for i in range(V):
			self.graph[i] = []
		self._V = V
		self.dst = [float('inf') for _ in range(V)]
		self.dst[s] = 0

	@property
	def dist(self):
		return self.dst

	@property
	def V(self):
		return self._V

	def add(self, a, b, cost):
		self.graph[a].append((b, cost))

	def shortest_path(self):
		for t in range(self.V):
			update = False
			for u in range(self.V):
				if self.dst[u] == float('inf'):
					continue
				for (v, cost) in self.graph[u]:
					if self.dst[v] > self.dst[u] + cost:
						self.dst[v] = self.dst[u] + cost
						update = True
						if t == self.V - 1 and v == self.V - 1:
							return True
			if not update:
				break
		return False

def solve():
	(N, M) = list(map(int, input().split()))
	bf = BellmanFord(0, N)
	for _ in range(M):
		(a, b, c) = list(map(int, input().split()))
		bf.add(a - 1, b - 1, -c)
	nloop = bf.shortest_path()
	if nloop:
		print('inf')
	else:
		print(-bf.dist[N - 1])

def __starting_point():
	solve()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline

def solve():
	(N, M) = list(map(int, rl().split()))
	graph = []
	for _ in range(M):
		(a, b, c) = list(map(int, rl().split()))
		a -= 1
		b -= 1
		c *= -1
		graph.append([a, b, c])

	def bellman_ford(s):
		dist_ls = [10 ** 15] * N
		dist_ls[s] = 0
		for i in range(N):
			for (s, t, w) in graph:
				if dist_ls[s] + w < dist_ls[t]:
					dist_ls[t] = dist_ls[s] + w
					if i == N - 1 and t == N - 1:
						return -1
		return dist_ls
	dist = bellman_ford(0)
	if dist == -1:
		print('inf')
	else:
		print(-1 * dist[-1])

def __starting_point():
	solve()
__starting_point()


def resolve():
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for i in range(m)]
	a = [[x, y, -z] for (x, y, z) in a]
	print(BF(a, n, 1)[-1])

def BF(p, n, s):
	inf = float('inf')
	d = [inf for i in range(n)]
	d[s - 1] = 0
	for i in range(n + 1):
		for e in p:
			if e[0] != inf and d[e[1] - 1] > d[e[0] - 1] + e[2]:
				d[e[1] - 1] = d[e[0] - 1] + e[2]
		if i == n - 1:
			t = d[-1]
		if i == n and t != d[-1]:
			return [0, 'inf']
	return list(map(lambda x: -x, d))
resolve()


(N, M) = map(int, input().split())
es = [tuple(map(int, input().split())) for i in range(M)]
INF = float('inf')
d = [INF] * N
d[0] = 0
for i in range(N):
	for (fr, to, cost) in es:
		(fr, to) = (fr - 1, to - 1)
		cost *= -1
		if d[fr] != INF and d[to] > d[fr] + cost:
			d[to] = d[fr] + cost
			if i == N - 1 and to == N - 1:
				print('inf')
				exit()
print(-d[-1])


(N, M) = map(int, input().split())
edges = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	edges.append((a, b, -c))
INF = 10 ** 9 * M * 10 * 2
d = [INF for _ in range(N + 1)]
d[1] = 0

def update():
	for edge in edges:
		(a, b, c) = edge
		d[b] = min(d[b], d[a] + c)
for _ in range(N - 1):
	update()
ansA = d[N]
for _ in range(N):
	update()
ansB = d[N]
if ansA == ansB:
	answer = -ansA
else:
	answer = 'inf'
print(answer)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
edge = [[] for i in range(m)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	edge[i] = [a - 1, b - 1, -c]
d = [float('inf')] * n
d[0] = 0
for _ in range(n):
	for i in range(m):
		(e0, e1, e2) = edge[i]
		d[e1] = min(d[e1], d[e0] + e2)
ans1 = d[-1]
for _ in range(n):
	for i in range(m):
		(e0, e1, e2) = edge[i]
		if d[e1] > d[e0] + e2:
			d[e1] = -float('inf')
ans2 = d[-1]
print('inf' if ans1 != ans2 else -ans1)


(n, m) = map(int, input().split())
inf = float('inf')
l = [tuple(map(int, input().split())) for i in range(m)]
d = [inf] * n
d[0] = 0
for i in range(n):
	for (a, b, c) in l:
		(a, b, c) = (a - 1, b - 1, -c)
		if d[a] != inf and d[b] > d[a] + c:
			d[b] = d[a] + c
			if i == n - 1 and b == n - 1:
				print('inf')
				exit()
print(-d[-1])


import sys
INF = float('inf')

def Bellmanford(n, edges, 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 -1 * d[n - 1]
(n, m) = map(int, input().split())
edges = [0] * m
for i in range(m):
	(a, b, c) = map(int, input().split())
	edges[i] = (a - 1, b - 1, -c)
ans = Bellmanford(n, edges, 0)
print(ans)


(N, M) = list(map(int, input().split()))
edge = [[] for _ in range(N)]
dist = [-float('inf') for _ in range(N)]
dist[0] = 0
for _ in range(M):
	(a, b, c) = list(map(int, input().split()))
	edge[a - 1].append((b - 1, c))
tmp = -float('inf')
for n in range(N):
	flag = 0
	tmp = dist[-1]
	for i in range(N):
		for (b, p) in edge[i]:
			if dist[b] < dist[i] + p:
				dist[b] = dist[i] + p
				flag = 1
	if flag == 0:
		break
if tmp != dist[-1]:
	print('inf')
else:
	print(int(dist[-1]))


(n, m) = map(int, input().split())
edges = [None] * m
for i in range(m):
	(a, b, c) = map(int, input().split())
	edges[i] = (a - 1, b - 1, -c)
INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n - 1):
	for (f, t, c) in edges:
		if d[f] == INF:
			continue
		d[t] = min(d[t], d[f] + c)
inf_flag = [False] * n
for i in range(n):
	for (f, t, c) in edges:
		if d[f] == INF:
			continue
		if inf_flag[f] == True:
			inf_flag[t] = True
		if d[t] > d[f] + c:
			d[t] = d[f] + c
			inf_flag[t] = True
print('inf' if inf_flag[n - 1] else -d[n - 1])


(n, m) = map(int, input().split())
e = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	e.append([a - 1, b - 1, -c])
M = 10 ** 18
d = [0] + [M] * ~-n
k = 0
v = 0
while k < n * 2:
	k += 1
	if k == n:
		v = d[-1]
	f = 0
	for (a, b, c) in e:
		if d[b] > d[a] + c:
			d[b] = d[a] + c
			f = 1
	if not f:
		break
if not v or v == d[-1]:
	print(-d[-1])
else:
	print('inf')


(n, m) = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]
inf = 10 ** 18
dis = [inf] * n
dis[0] = 0
for z in range(2 * n + 1):
	update = False
	for (a, b, c) in edge:
		a -= 1
		b -= 1
		if dis[a] != inf and dis[b] > dis[a] - c:
			dis[b] = dis[a] - c
			update = True
			if b == n - 1 and z >= n - 1:
				print('inf')
				exit()
print(-dis[n - 1])


def BellmanFord(x, n, s):
	inf = float('inf')
	dist = [inf for i in range(n + 1)]
	dist[s] = 0
	for i in range(1, n + 1):
		for (j, k, c) in x:
			if j != inf and dist[k] > dist[j] + c:
				dist[k] = dist[j] + c
				if i == n and k == n:
					return -1
	return dist
(n, m) = (int(i) for i in input().split())
x = []
for _ in range(m):
	(i, j, k) = (int(l) for l in input().split())
	x.append([i, j, -k])
b = BellmanFord(x, n, 1)
if b == -1:
	print('inf')
else:
	print(-b[n])


(n, m) = map(int, input().split())
dist = [-10 ** 18] * n
edge = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	edge.append((a - 1, b - 1, c))
dist[0] = 0
for i in range(n):
	for i in edge:
		(a, b, c) = i
		if dist[a] + c > dist[b]:
			dist[b] = dist[a] + c
			updated = True
ans = dist[n - 1]
for i in range(n):
	for i in edge:
		(a, b, c) = i
		if dist[a] + c > dist[b]:
			dist[b] = dist[a] + c
			updated = True
if ans == dist[n - 1]:
	print(dist[n - 1])
else:
	print('inf')


def main():
	(N, M) = map(int, input().split())
	g = []
	d = [float('INF')] * (N + 1)
	d[1] = 0
	for _ in range(M):
		(a, b, c) = 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()


(N, M) = [int(s) for s in input().split()]
dist = [N * -10 ** 9] * N
E = []
flag = 0
change = 0
N_flag = 0
for i in range(M):
	(a, b, c) = [int(s) for s in input().split()]
	E.append((a, b, c))
dist[0] = 0
for i in range(N):
	for (a, b, c) in E:
		if a == N or b == N:
			N_flag = 1
		newLen = dist[a - 1] + c
		if newLen > dist[b - 1]:
			change = 1
			dist[b - 1] = newLen
			if i == N - 1 and change == 1 and (N_flag == 1):
				flag = 1
		change = 0
		N_flag = 0
if flag == 1:
	print('inf')
else:
	print(dist[N - 1])


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = sys.stdin.readline

def resolve():
	(n, m) = map(int, input().split())
	dist = [float('inf')] * n
	dist[0] = 0
	edges = [0] * m
	for i in range(m):
		(a, b, c) = map(int, input().split())
		edges[i] = [a - 1, b - 1, -c]
	for k in range(1, 2 * n):
		for (u, v, cost) in edges:
			if dist[v] > dist[u] + cost:
				dist[v] = dist[u] + cost
		if k == n - 1:
			ans = dist[n - 1]
	print(-ans if ans == dist[n - 1] else 'inf')
resolve()


(n, m) = map(int, input().split())
std = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	std += [[a, b, -c]]

def bellman_ford(s):
	dist = [float('inf')] * n
	dist[s] = 0
	for u in range(n):
		for (s, t, d) in std:
			if dist[t] > dist[s] + d:
				dist[t] = dist[s] + d
				if u == n - 1 and t == n - 1:
					return -1
	return dist
dist = bellman_ford(0)
if dist != -1:
	print(-dist[n - 1])
else:
	print('inf')


(n, m) = [int(item) for item in input().split()]
edge = []
inf = 2000 * 10 ** 10
for i in range(m):
	(a, b, c) = [int(item) for item in input().split()]
	edge.append([a - 1, b - 1, -c])

def BellmanFord(start):
	dist = [inf for i in range(n)]
	dist[0] = 0
	for i in range(n):
		for (u, v, c) in edge:
			if dist[u] != inf and dist[u] + c < dist[v]:
				dist[v] = dist[u] + c
				if i == n - 1 and v == n - 1:
					return 'inf'
	return -dist[-1]
ret = BellmanFord(0)
print(ret)


(n, m) = map(int, input().split())
abc = [tuple(map(int, input().split())) for _ in range(m)]
Inf = float('inf')
dist = [Inf] * n
dist[0] = 0
for i in range(n):
	for (a, b, c) in abc:
		(a, b, c) = (a - 1, b - 1, -c)
		if dist[b] > dist[a] + c:
			dist[b] = dist[a] + c
			if i == n - 1 and b == n - 1:
				print('inf')
				return
print(-dist[-1])


(N, M) = map(int, input().split())
INF = float('inf')
d = [INF] * N
edges = [None] * M
for i in range(M):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	edges[i] = (a, b, -c)
d[0] = 0
for cnt in range(N):
	update = False
	for i in range(M):
		(a, b, c) = edges[i]
		if d[b] > d[a] + c:
			d[b] = d[a] + c
			update = True
			if cnt == N - 1 and b == N - 1:
				print('inf')
				exit(0)
	if not update:
		break
print(-d[N - 1])


import sys
(N, M) = list(map(int, input().split()))
edge = []
for s in sys.stdin.readlines():
	(a, b, c) = list(map(int, s.split()))
	edge.append((a - 1, b - 1, c))
path = [-float('inf')] * N
path[0] = 0
for i in range(N - 1):
	for j in range(M):
		(a, b, c) = edge[j]
		if path[b] < path[a] + c:
			path[b] = path[a] + c
for i in range(N - 1):
	for j in range(M):
		(a, b, c) = edge[j]
		if path[b] < path[a] + c:
			path[b] = float('inf')
print(path[-1])


(N, M) = map(int, input().split())
Edges = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	c = -c
	Edges.append([a, b, c])
dist = [float('inf')] * N
dist[0] = 0
for i in range(N):
	for (fr, to, cost) in Edges:
		if dist[fr] != float('inf') and dist[to] > dist[fr] + cost:
			dist[to] = dist[fr] + cost
			if (i == N - 1) & (to == N - 1):
				print('inf')
				exit()
print(-dist[-1])


ai_ = lambda : [int(x) - 1 for x in input().split()]
ai = lambda : list(map(int, input().split()))
(n, m) = ai()
from collections import defaultdict as dd
edge = dd(list)
for _ in range(m):
	(a, b, c) = ai()
	edge[a - 1].append([b - 1, -c])
dist = [float('inf')] * n
dist[0] = 0
for i in range(n):
	for cur_v in range(n):
		for (v, c) in edge[cur_v]:
			if dist[v] > dist[cur_v] + c:
				dist[v] = dist[cur_v] + c
				if i == n - 1 and v == n - 1:
					print('inf')
					exit()
print(-dist[-1])


(n, m) = map(int, input().split())
es = [list(map(int, input().split())) for _ in range(m)]
inf = float('inf')
d = [-inf] * (n + 1)
d[1] = 0

def bellman_ford():
	for i in range(n):
		isUpdated = False
		for (e_from, e_to, cost) in es:
			if d[e_to] < d[e_from] + cost:
				d[e_to] = d[e_from] + cost
				isUpdated = True
				if i == n - 1 and e_to == n:
					return inf
		if not isUpdated:
			break
	return d[n]
print(bellman_ford())


(N, M) = map(int, input().split())
edges = []
for _ in range(M):
	(u, v, c) = map(int, input().split())
	edges.append((-c, u - 1, v - 1))
INF = float('inf')
dist = [INF] * N
dist[0] = 0
for _ in range(N - 1):
	for (c, u, v) in edges:
		if dist[v] > c + dist[u]:
			dist[v] = c + dist[u]
neg_cycle = [False] * N
for (c, u, v) in edges:
	if dist[v] > c + dist[u]:
		dist[v] = c + dist[u]
		neg_cycle[u] = True
		neg_cycle[v] = True
if neg_cycle[N - 1]:
	print('inf')
else:
	print(-dist[N - 1])


import sys
sys.setrecursionlimit(10 ** 7)
(N, M) = list(map(int, input().split()))
R = [[] for _ in range(N)]
for _ in range(M):
	(a, b, c) = list(map(int, input().split()))
	R[a - 1].append((b - 1, c))
INF = 10 ** 40
S = [-INF] * N
S[0] = 0

def score(fst, s, C):
	for (nx, p) in R[fst]:
		if S[nx] >= s + p or S[nx] >= INF:
			continue
		S[nx] = s + p
		if nx in C:
			S[nx] = INF
		C[nx] = C.get(nx, 0) + 1
		score(nx, S[nx], C)
		C[nx] -= 1
		if C[nx] == 0:
			del C[nx]
score(0, 0, {0: 1})
if S[-1] < INF:
	ans = S[-1]
else:
	ans = 'inf'
print(ans)


inf = 10 ** 20
(n, m) = map(int, input().split())
a_list = []
d = [-inf for _ in range(n)]
d[0] = 0
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	a_list.append([a, b, c])
	d[b] = max(d[a] + c, d[b])
temp = d[-1]
for i in range(m):
	(a, b, c) = a_list[i]
	d[b] = max(d[a] + c, d[b])
if temp != d[-1]:
	print('inf')
else:
	print(d[-1])


def bellman_ford():
	(n, m) = list(map(int, input().split()))
	g = [[] for _ in range(n)]
	for i in range(m):
		(a, b, c) = list(map(int, input().split()))
		g[a - 1].append([b - 1, -1 * c])
	dist = [float('inf')] * n
	inf = float('inf')
	dist[0] = 0
	for i in range(n):
		for v in range(n):
			for k in range(len(g[v])):
				edge = g[v][k]
				if dist[v] != inf and dist[v] + edge[1] < dist[edge[0]]:
					dist[edge[0]] = dist[v] + edge[1]
	ans = dist[n - 1]
	neg = [0] * n
	for i in range(n):
		for edge in g[i]:
			if dist[i] == inf:
				continue
			if dist[i] + edge[1] < dist[edge[0]]:
				dist[edge[0]] = dist[i] + edge[1]
				neg[edge[0]] = 1
			if neg[i]:
				neg[edge[0]] = 1
	if not neg[n - 1]:
		print(dist[n - 1] * -1)
	else:
		print('inf')
	return False

def main():
	bellman_ford()

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(m)]
dist = [-float('inf')] * (n + 1)
dist[1] = 0
for i in range(n):
	for (a, b, c) in ABC:
		if dist[b] < dist[a] + c:
			if i == n - 1 and b == n:
				print('inf')
				return
			dist[b] = dist[a] + c
ans = dist[n]
print(ans)


def bf(edges, start, N):
	INF = float('inf')
	costs = [INF] * N
	costs[start] = 0
	for i in range(N):
		for (f, t, c) in edges:
			if costs[f] != INF and costs[f] + c < costs[t]:
				costs[t] = costs[f] + c
				if i == N - 1 and t == N - 1:
					return 'inf'
	return -costs[N - 1]
(N, M) = map(int, input().split())
edges = []
for _ in range(M):
	(f, t, c) = map(int, input().split())
	edges.append((f - 1, t - 1, -c))
print(bf(edges, 0, N))


(N, M) = map(int, input().split())
edges = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	edges.append((a, b, c))
cost = [-float('INF')] * (N + 1)
cost[1] = 0
cnt = 0
flag = True
for _ in range(N):
	for (a, b, c) in edges:
		if cost[a] + c > cost[b]:
			cost[b] = cost[a] + c
tmp = cost[N]
for _ in range(N):
	for (a, b, c) in edges:
		if cost[a] + c > cost[b]:
			cost[b] = cost[a] + c
if tmp < cost[N]:
	print('inf')
else:
	print(tmp)


def BF(p, n, s):
	inf = float('inf')
	d = [inf for i in range(n)]
	d[s - 1] = 0
	for i in range(n + 1):
		for e in p:
			if e[0] != inf and d[e[1] - 1] > d[e[0] - 1] + e[2]:
				d[e[1] - 1] = d[e[0] - 1] + e[2]
		if i == n - 1:
			t = d[-1]
		if i == n and t != d[-1]:
			return [0, 'inf']
	return list(map(lambda x: -x, d))
(n, m) = map(int, input().split())
g = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	g.append([a, b, -c])
print(BF(g, n, 1)[-1])


(n, m) = map(int, input().split())
abc = []
for i in range(m):
	abc.append([int(j) for j in input().split()])
b = [float('INF')] * (n + 1)
b[1] = 0
for i in range(1, n + 1):
	for (s, t, u) in abc:
		if b[t] > b[s] - u:
			b[t] = b[s] - u
			if i == n and t == n:
				print('inf')
				exit()
print(-b[-1])


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 6)
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
nn = lambda : list(stdin.readline().split())
ns = lambda : stdin.readline().rstrip()
(n, m) = na()
abc = [tuple(na()) for i in range(m)]
dp = [float('inf')] * n
dp[0] = 0
for i in range(n):
	for (a, b, c) in abc:
		(a, b, c) = (a - 1, b - 1, -c)
		if dp[a] != float('inf') and dp[b] > dp[a] + c:
			dp[b] = dp[a] + c
			if i == n - 1 and b == n - 1:
				print('inf')
				exit()
print(-dp[-1])


class Edge:

	def __init__(self, from_node, to_node, weight):
		self.from_node = from_node
		self.to_node = to_node
		self.weight = weight

def bellman_ford(N, edges, start, goal):
	MIN_INF = -10 ** 15
	d = [MIN_INF for _ in range(N)]
	d[start] = 0
	for loop in range(N):
		updated = False
		goal_updated = False
		for edge in edges:
			new_d = edge.weight + d[edge.from_node]
			if d[edge.to_node] < new_d:
				d[edge.to_node] = new_d
				updated = True
				if edge.to_node == goal:
					goal_updated = True
		if not updated:
			return d[goal]
		if loop == N - 1:
			if not goal_updated:
				return d[goal]
			return None

def main():
	(N, M) = list(map(int, input().split(' ')))
	edges = list()
	for _ in range(M):
		(a, b, c) = list(map(int, input().split(' ')))
		from_node = a - 1
		to_node = b - 1
		weight = c
		edges.append(Edge(from_node, to_node, weight))
	(start, goal) = (0, N - 1)
	result = bellman_ford(N, edges, start, goal)
	if result is None:
		print('inf')
	else:
		print(result)

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
inf = 10 ** 18
edges = []
for m in range(M):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, -c))
dist = [inf] * N
dist[0] = 0
update = False
for i in range(N):
	for (a, b, c) in edges:
		if dist[b] > dist[a] + c:
			dist[b] = dist[a] + c
			if b == N - 1 and i == N - 1:
				update = True
if update:
	print('inf')
else:
	print(-dist[N - 1])


def bellman_ford(edges, start, n):
	inf = float('INF')
	costs = [inf] * n
	costs[start] = 0
	for e in edges:
		(u, v, c) = e
		if costs[v] > costs[u] + c:
			costs[v] = costs[u] + c
	ans = costs[-1]
	for (u, v, c) in edges:
		if costs[v] > costs[u] + c:
			costs[v] = costs[u] + c
	return -ans if costs[-1] == ans else 'inf'
(n, m) = map(int, input().split())
edges = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, -c))
print(bellman_ford(edges, 0, n))


import sys
inf = float('inf')
(n, m) = map(int, sys.stdin.readline().split())
abc = []
for _ in range(m):
	(a, b, c) = map(int, sys.stdin.readline().split())
	abc.append((a - 1, b - 1, -c))

def main():
	dist = [inf] * n
	dist[0] = 0
	for _ in range(n - 1):
		for (a, b, c) in abc:
			dist[b] = min(dist[b], dist[a] + c)
	for _ in range(n):
		for (a, b, c) in abc:
			if dist[a] + c < dist[b]:
				dist[b] = -inf
	return -dist[n - 1]
ans = main()
print(ans)


def Bellman_Ford(s, g, inf=1 << 60):
	N = len(g)
	dist = [inf] * N
	dist[s] = 0
	for _ in range(N):
		not_updated = True
		for v in range(N):
			for (u, c) in g[v]:
				if dist[v] == inf or dist[v] + c >= dist[u]:
					continue
				dist[u] = dist[v] + c
				not_updated = False
		if not_updated:
			return -dist[N - 1]
	ret = dist[N - 1]
	for _ in range(N):
		not_updated = True
		for v in range(N):
			for (u, c) in g[v]:
				if dist[v] == inf or dist[v] + c >= dist[u]:
					continue
				dist[u] = dist[v] + c
				not_updated = False
		if not_updated:
			break
	if ret == dist[N - 1]:
		return -ret
	else:
		return 'inf'

def main():
	import sys
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 7)
	(N, M) = list(map(int, input().split()))
	g = tuple((set() for _ in range(N)))
	for _ in range(M):
		(a, b, c) = list(map(int, input().split()))
		a -= 1
		b -= 1
		g[a].add((b, -c))
	ans = Bellman_Ford(s=0, g=g)
	print(ans)

def __starting_point():
	main()
__starting_point()


def BellmanFord(edges, num_v, source):
	dist = [float('inf') for i in range(num_v)]
	dist[source] = 0
	for i in range(num_v):
		for edge in edges:
			if edge[0] != float('inf') and dist[edge[1]] > dist[edge[0]] + edge[2]:
				dist[edge[1]] = dist[edge[0]] + edge[2]
				if i == num_v - 1 and edge[1] == N - 1:
					return -1
	return dist
(N, M) = map(int, input().split())
edges = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	edges.append([a - 1, b - 1, -c])
d = BellmanFord(edges, N, 0)
if d == -1:
	print('inf')
	exit()
print(-d[N - 1])


inf = float('inf')
(N, M) = map(int, input().split())
edges = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))
d = [-inf] * N
d[0] = 0
for i in range(N):
	for (a, b, c) in edges:
		if d[b] < d[a] + c:
			d[b] = d[a] + c
for i in range(N):
	for (a, b, c) in edges:
		if d[b] < d[a] + c:
			d[b] = inf
print(d[N - 1])


(N, M) = map(int, input().split())
E = [list(map(int, input().split())) for m in range(M)]
dp = (N + 1) * [float('inf')]
dp[1] = 0
for n in range(N):
	for (a, b, c) in E:
		dp[b] = min(dp[b], dp[a] - c)
x = dp[N]
for (a, b, c) in E:
	dp[b] = min(dp[b], dp[a] - c)
if x != dp[N]:
	print('inf')
else:
	print(-x)


import sys
sys.setrecursionlimit(10 ** 7)

def main():
	(N, M) = list(map(int, input().split()))
	G = [[] for _ in range(N)]
	for _ in range(M):
		(a, b, c) = list(map(int, input().split()))
		G[a - 1].append((b - 1, c))
	INF = 10 ** 40
	S = [-INF] * N
	S[0] = 0

	def helper(n, s, hist):
		for (g, gc) in G[n]:
			if S[g] >= s + gc or S[g] >= INF:
				continue
			S[g] = s + gc
			if g in hist:
				S[g] = INF
			hist[g] = hist.get(g, 0) + 1
			helper(g, S[g], hist)
			hist[g] -= 1
			if hist[g] == 0:
				del hist[g]
	helper(0, 0, {0: 1})
	s = S[-1]
	return s if s < INF else 'inf'
print(main())


(N, M) = map(int, input().split())
INF = float('inf')
start = []
end = []
weight = []
node_cost = [-INF] * N
for _ in range(M):
	(a, b, c) = map(int, input().split())
	start.append(a - 1)
	end.append(b - 1)
	weight.append(c)
node_cost[0] = 0
for _ in range(N - 1):
	for i in range(M):
		new_cost = node_cost[start[i]] + weight[i]
		if new_cost > node_cost[end[i]]:
			node_cost[end[i]] = new_cost
ans = node_cost[N - 1]
cycle = [False] * N
for _ in range(N):
	for i in range(M):
		if cycle[start[i]]:
			cycle[end[i]] = True
		new_cost = node_cost[start[i]] + weight[i]
		if new_cost > node_cost[end[i]]:
			cycle[end[i]] = True
if cycle[N - 1]:
	ans = 'inf'
print(ans)


(n, m) = list(map(int, input().split()))
(li, lis, lisa) = ([], [], [])
for o in range(m):
	(a, b, c) = list(map(int, input().split()))
	li.append(a)
	lis.append(b)
	lisa.append(c)
cou = [-float('inf') for i in range(n + 1)]
cou[1] = 0
key = True
for i in range(n - 1):
	for k in range(m):
		cou[lis[k]] = max(cou[lis[k]], cou[li[k]] + lisa[k])
co = cou[n]

def ans():
	for l in range(m):
		cou[lis[l]] = max(cou[lis[l]], cou[li[l]] + lisa[l])
	if cou[n] > co:
		return 'inf'
	return cou[n]
print(ans())


import sys
input = sys.stdin.readline

def readlines(n):
	for _ in range(n):
		(a, b, c) = map(int, input().split())
		yield (a, b, c)

def main():
	(n, m) = map(int, input().split())
	edges = [(a - 1, b - 1, -c) for (a, b, c) in readlines(m)]
	costs = bellman_ford(0, edges, n)
	if costs == -1:
		print('inf')
	else:
		print(-costs[-1])

def bellman_ford(start, edges, n):
	inf = float('inf')
	costs = [inf] * n
	costs[start] = 0
	for i in range(n):
		for (u, v, weight) in edges:
			if costs[u] + weight < costs[v]:
				costs[v] = costs[u] + weight
				if i == n - 1 and v == n - 1:
					return -1
	return costs
main()


(N, M) = map(int, input().split())
E = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	E.append((a, b, c))
dist = [-N * 10 ** 9] * (N + 1)
dist[1] = 0
flag = False
for i in range(N):
	for (a, b, c) in E:
		newlen = dist[a] + c
		if newlen > dist[b]:
			dist[b] = newlen
	if i == N - 1 and dist[N] > predist:
		flag = True
	predist = dist[N]
if flag:
	print('inf')
else:
	print(dist[N])


(N, M) = map(int, input().split())
E = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	E.append((a - 1, b - 1, -c))
INF = 10 ** 20
V = [INF] * N
V[0] = 0
for _ in range(N):
	for (a, b, c) in E:
		d = V[a] + c
		if d < V[b]:
			V[b] = d
R = [False] * N
R[-1] = True
for _ in range(N):
	for (a, b, c) in E:
		R[a] |= R[b]
for (a, b, c) in E:
	if V[a] + c < V[b] and R[b]:
		print('inf')
		exit()
print(-V[-1])


(n, m) = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(m)]
d = [0] + [-float('inf')] * (n - 1)
for _ in range(n - 1):
	for (a, b, c) in e:
		d[b - 1] = max(d[b - 1], d[a - 1] + c)
r = d[n - 1]
for _ in range(n - 1):
	for (a, b, c) in e:
		d[b - 1] = max(d[b - 1], d[a - 1] + c)
if d[n - 1] == r:
	print(r)
else:
	print('inf')


(n, m) = map(int, input().split())
edges = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, -c))

def shortest_path(v, s, edges, inf):
	d = [inf] * v
	d[s] = 0
	for i in range(2 * n):
		update = False
		for (frm, to, cost) in edges:
			if d[frm] != inf and d[to] > d[frm] + cost:
				d[to] = d[frm] + cost
				update = True
		if i == n:
			memo = d[-1]
	if memo != d[-1]:
		print('inf')
		exit()
	return d[-1]
inf = 1e+30
print(-shortest_path(n, 0, edges, inf))


(n, m) = map(int, input().split())
vve = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n + 1)]
for (a, b, e) in vve:
	graph[a].append((b, -e))
score = [10 ** 15 for i in range(n + 1)]
score[1] = 0
for j in range(n + 1):
	flg = 0
	for i in range(m):
		(v1, v2, e) = vve[i]
		e = -e
		if score[v1] != 10 ** 15 and score[v2] > score[v1] + e:
			score[v2] = score[v1] + e
			flg = 1
			if j == n - 1:
				p = -score[n]
			if j == n:
				q = -score[n]
	if flg == 0:
		break
if flg == 0:
	print(-score[n])
elif p == q:
	print(p)
else:
	print('inf')


(n, m) = map(int, input().split())
edge = [[] for i in range(n + 1)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	edge[a].append((b, -c))
renew = [0] * (n + 1)
INF = float('inf')

def bellmanford(s, n):
	d = [INF for i in range(n + 1)]
	d[s] = 0
	q = [s]
	while q:
		x = q.pop()
		dist = d[x]
		for (v, cost) in edge[x]:
			if d[v] > dist + cost:
				d[v] = dist + cost
				q.append(v)
				renew[v] += 1
				if renew[v] > n:
					d[v] = -INF
	return d
d = bellmanford(1, n)
print(-d[n])


(N, M) = map(int, input().split())
adjacent = []
score = ['None' for i in range(N)]
score[0] = 0
for i in range(M):
	(a, b, c) = map(int, input().split())
	adjacent.append([a - 1, b - 1, c])
for i in range(N):
	for j in adjacent:
		if score[j[1]] == 'None' and score[j[0]] != 'None':
			score[j[1]] = score[j[0]] + j[2]
		if score[j[1]] != 'None' and score[j[0]] != 'None':
			if score[j[1]] < score[j[0]] + j[2]:
				score[j[1]] = score[j[0]] + j[2]
	if i == N - 2:
		t = score[N - 1]
	if i == N - 1:
		if t != score[N - 1]:
			score[N - 1] = 1000000000000000.0
if score[N - 1] < 1000000000000000.0:
	print(t)
else:
	print('inf')


import sys
(n, m) = map(int, input().split())
weights = {}
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	weights[a, b] = c
score = [-10 ** 50] * n
score[0] = 0
pred = [-1] * n
for i in range(n):
	for (edge, c) in weights.items():
		(a, b) = edge
		if score[b] < score[a] + c:
			score[b] = score[a] + c
			pred[b] = a
res = score[n - 1]
b = n - 1
while b != 0:
	a = pred[b]
	c = weights[a, b]
	if score[b] < score[a] + c:
		res = 'inf'
		break
	b = a
print(res)


(N, M) = map(int, input().split())
road = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	road.append((a - 1, b - 1, -c))
INF = 10 ** 15
d = [INF] * N
d[0] = 0

def bellman_ford():
	nonlocal d
	for i in range(N):
		for (a, b, c) in road:
			d[b] = min(d[b], d[a] + c)
bellman_ford()
for (a, b, c) in road:
	new_d = d[a] + c
	if new_d < d[b]:
		d[b] = -float('inf')
bellman_ford()
if d[-1] > -float('inf'):
	print(int(-d[-1]))
else:
	print('inf')


(n, m) = map(int, input().split())
INF = float('inf')
G = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	G.append([a - 1, b - 1, -c])

def bellmanFord(G, s):
	D = [INF for i in range(n)]
	D[s] = 0
	for i in range(1, n):
		for (x, y, z) in G:
			D[y] = min(D[y], D[x] + z)
	ans = -D[n - 1]
	for (x, y, z) in G:
		D[y] = min(D[y], D[x] + z)
	if ans != -D[n - 1]:
		return -1
	else:
		return -D[n - 1]
ans = bellmanFord(G, 0)
if ans == -1:
	print('inf')
else:
	print(ans)


(n, m) = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
score = [-float('inf')] * (n + 1)
score[1] = 0
cnt = 0
for i in range(n):
	for (frm, to, cost) in edges:
		if score[to] < score[frm] + cost:
			if i == n - 1 and to == n:
				print('inf')
				exit()
			score[to] = score[frm] + cost
print(score[n])


(v, e) = map(int, input().split())
r = 0
INF = 10 ** 18
edges = [[] for i in range(v)]
(a, b, c) = ([], [], [])
d = [INF for i in range(v)]
for _ in range(e):
	(s, t, d_) = map(int, input().split())
	edges[s - 1].append((t - 1, d_ * -1))
	a.append(s - 1)
	b.append(t - 1)
	c.append(d_ * -1)
f = False
d[r] = 0
for _ in range(v):
	for u in range(v):
		if d[u] != INF:
			for (to, dist) in edges[u]:
				d[to] = min(d[to], d[u] + dist)
nega = [False] * v
for _ in range(v):
	for i in range(e):
		if d[a[i]] == INF:
			continue
		if d[b[i]] > d[a[i]] + c[i]:
			d[b[i]] = d[a[i]] + c[i]
			nega[b[i]] = True
		if nega[a[i]]:
			nega[b[i]] = True
if nega[-1]:
	print('inf')
else:
	print(d[-1] * -1)


(n, m) = map(int, input().split())
a = []
b = []
c = []
for _ in range(m):
	(x, y, z) = map(int, input().split())
	a.append(x - 1)
	b.append(y - 1)
	c.append(z * -1)
d = [float('inf')] * n
d[0] = 0
for x in range(n * 2):
	for i in range(m):
		if d[a[i]] + c[i] < d[b[i]]:
			d[b[i]] = d[a[i]] + c[i]
			if n - 1 <= x and b[i] == n - 1:
				print('inf')
				exit(0)
print(d[n - 1] * -1)


inf = float('inf')
(N, M) = map(int, input().split())
info = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	info.append((a, b, c))
dist = [-inf for _ in range(N)]
dist[0] = 0
for i in range(N):
	for (v, nv, w) in info:
		if dist[nv] < dist[v] + w:
			dist[nv] = dist[v] + w
			if i == N - 1 and nv == N - 1:
				print('inf')
				exit()
ans = dist[N - 1]
print(ans)


(N, M) = map(int, input().split())
E = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	c = -c
	E.append([a, b, c])
dist = [float('inf')] * (N + 1)
dist[0] = 0
for n in range(N):
	for (a, b, c) in E:
		if (dist[a] != float('inf')) & (dist[b] > dist[a] + c):
			dist[b] = dist[a] + c
			if (n == N - 1) & (b == N - 1):
				print('inf')
				exit()
print(-dist[N - 1])


import sys

class DSU:

	def __init__(self, n):
		self._n = n
		self.parent_or_size = [-1] * n

	def merge(self, a, b):
		assert 0 <= a < self._n
		assert 0 <= b < self._n
		(x, y) = (self.leader(a), self.leader(b))
		if x == y:
			return x
		if -self.parent_or_size[x] < -self.parent_or_size[y]:
			(x, y) = (y, x)
		self.parent_or_size[x] += self.parent_or_size[y]
		self.parent_or_size[y] = x
		return x

	def same(self, a, b):
		assert 0 <= a < self._n
		assert 0 <= b < self._n
		return self.leader(a) == self.leader(b)

	def leader(self, a):
		assert 0 <= a < self._n
		if self.parent_or_size[a] < 0:
			return a
		self.parent_or_size[a] = self.leader(self.parent_or_size[a])
		return self.parent_or_size[a]

	def size(self, a):
		assert 0 <= a < self._n
		return -self.parent_or_size[self.leader(a)]

	def groups(self):
		leader_buf = [self.leader(i) for i in range(self._n)]
		result = [[] for _ in range(self._n)]
		for i in range(self._n):
			result[leader_buf[i]].append(i)
		return [r for r in result if r != []]

class Fenwick_Tree:

	def __init__(self, n):
		self._n = n
		self.data = [0] * n

	def add(self, p, x):
		assert 0 <= p < self._n
		p += 1
		while p <= self._n:
			self.data[p - 1] += x
			p += p & -p

	def sum(self, l, r):
		assert 0 <= l <= r <= self._n
		return self._sum(r) - self._sum(l)

	def _sum(self, r):
		s = 0
		while r > 0:
			s += self.data[r - 1]
			r -= r & -r
		return s
INF = float('inf')

def Bellmanford(n, edges, 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)


(N, M) = map(int, input().split())
edges = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	edges.append((a, b, c))
edges.sort()

def bellmanford(n, edges, start):
	INF = float('inf')
	dist = [-INF] * (n + 1)
	dist[start] = 0
	for i in range(n):
		for (pre, ne, weight) in edges:
			if dist[pre] != -INF and dist[pre] + weight > dist[ne]:
				dist[ne] = dist[pre] + weight
				if i == n - 1 and ne == n:
					return 'inf'
	return dist[n]
answer = bellmanford(N, edges, 1)
print(answer)


def bellman_ford(s):
	d = [float('inf')] * (N + 1)
	d[s] = 0
	nega = [0 for i in range(N + 1)]
	for i in range(N + 1):
		update = False
		for (x, y, z) in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
				nega[y] += 1
		if not update:
			break
		if i == N:
			d[0] = -1
	return [d, nega]
(N, M) = map(int, input().split())
g = []
for _ in range(M):
	(x, y, z) = [int(x) for x in input().split()]
	g.append([x, y, -z])
ans = bellman_ford(1)
if ans[1][-1] > 1:
	print('inf')
else:
	print(int(-ans[0][-1]))


def cin():
	return list(map(int, input().split()))

def bellman_ford(s):
	d = [float('inf')] * N
	d[s] = 0
	for i in range(N):
		update = False
		for (x, y, z) in G:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				if i == N - 1 and y == N - 1:
					return 'inf'
	return -d[N - 1]
(N, M) = cin()
G = []
bfr = []
for i in range(M):
	(s, t, w) = cin()
	G.append((s - 1, t - 1, -w))
ans = bellman_ford(0)
print(ans)


(N, M) = map(int, input().split())
adj = [[] for i in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	adj[a - 1].append((b - 1, c))
INF = float('inf')
cost = [-INF for i in range(N)]
cost[0] = 0
prev = [None for i in range(N)]
for i in range(N):
	for v in [v for v in range(N) if cost[v] != -INF]:
		for (v2, c) in adj[v]:
			if cost[v2] < cost[v] + c:
				cost[v2] = cost[v] + c
				prev[v2] = v
v = N - 1
for i in range(N):
	v = prev[v]
	if v == None:
		print(cost[N - 1])
		break
else:
	print('inf')


(N, M, *L) = map(int, open(0).read().split())
dic = [[] for i in range(N + 1)]
rdic = [[] for i in range(N + 1)]
for (a, b, c) in zip(*[iter(L)] * 3):
	dic[a].append(b)
	rdic[b].append(a)
ok1 = [False] * (N + 1)
ok1[1] = True
q = [1]
while q:
	p = q.pop()
	for v in dic[p]:
		if not ok1[v]:
			ok1[v] = True
			q.append(v)
ok2 = [False] * (N + 1)
ok2[N] = True
q = [N]
while q:
	p = q.pop()
	for v in rdic[p]:
		if not ok2[v]:
			ok2[v] = True
			q.append(v)
ok = [a & b for (a, b) in zip(ok1, ok2)]
cnt = 0
dist = [-10 ** 20] * (N + 1)
dist[1] = 0
while True:
	flag = True
	for (a, b, c) in zip(*[iter(L)] * 3):
		if ok[a] & ok[b] and ok[a] != -10 ** 20 and (dist[b] < dist[a] + c):
			flag = False
			dist[b] = dist[a] + c
	if flag:
		print(dist[N])
		break
	cnt += 1
	if cnt > N:
		print('inf')
		break


(N, M) = map(int, input().split())
INF = float('inf')
es = [tuple(map(int, input().split())) for i in range(M)]
ds = [INF] * N
ds[0] = 0
for i in range(N):
	for (a, b, c) in es:
		(a, b, c) = (a - 1, b - 1, -c)
		if ds[a] != INF and ds[b] > ds[a] + c:
			ds[b] = ds[a] + c
			if i == N - 1 and b == N - 1:
				print('inf')
				exit()
print(-ds[-1])


(n, m) = map(int, input().split())
list_edge = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	list_edge.append((a - 1, b - 1, -c))
list_point = [float('inf') if i != 0 else 0 for i in range(n)]
for i in range(n + 1):
	for (a, b, c) in list_edge:
		if list_point[a] != float('Inf') and list_point[b] > list_point[a] + c:
			list_point[b] = list_point[a] + c
			if i == n and b == n - 1:
				print('inf')
				exit()
print(-1 * list_point[-1])


INF = -float('inf')

def Bellmanford(n, e):
	dp = [INF] * n
	dp[0] = 0
	for i in range(n):
		for (a, b, c) in e:
			if dp[a] != INF and dp[a] + c > dp[b]:
				dp[b] = dp[a] + c
				if i == n - 1 and b == n - 1:
					return 'inf'
	return dp[n - 1]
(N, M) = map(int, input().split())
abc = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	abc.append((a - 1, b - 1, c))
ans = Bellmanford(N, abc)
print(ans)


(n, m) = map(int, input().split())
graph = [tuple(map(int, input().split())) for _ in range(m)]

def shortest_path(s):
	MIN = -1 * 10 ** 12
	d = [MIN] * (n + 1)
	d[s] = 0
	update = True
	cnt = 1
	tmp = MIN
	while update:
		update = False
		for (a, b, c) in graph:
			if d[a] != MIN and d[b] < d[a] + c:
				d[b] = d[a] + c
				update = True
		if cnt == m:
			tmp = d[n]
		if update and cnt == 2 * m and (d[n] > tmp):
			return 'inf'
		if cnt == 2 * m:
			update = False
		cnt += 1
	return d[n]
print(shortest_path(1))


def shortest_path(edge, num_v, start):
	inf = float('inf')
	d = [-inf for f in range(num_v)]
	d[start] = 0
	for i in range(3000):
		update = False
		for e in edge:
			if d[e[0] - 1] != -inf and d[e[1] - 1] < d[e[0] - 1] + e[2]:
				d[e[1] - 1] = d[e[0] - 1] + e[2]
				update = True
				if e[1] == n and i >= n:
					return 'inf'
		if not update:
			break
	return d[-1]
(n, m) = map(int, input().split())
p = []
for i in range(m):
	p.append(list(map(int, input().split())))
ans = shortest_path(p, n, 0)
print(ans)


(N, M) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(M)]
INF = -float('inf')
dist = [INF] * N
dist[0] = 0
d_tmp = 0
for abci in abc:
	if dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
		dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]
d_tmp = dist[-1]
for abci in abc:
	if dist[abci[0] - 1] != INF and dist[abci[1] - 1] < dist[abci[0] - 1] + abci[2]:
		dist[abci[1] - 1] = dist[abci[0] - 1] + abci[2]
print(dist[-1]) if d_tmp == dist[-1] else print('inf')


def solve(V, E, r, edges):
	cost = [-float('inf')] * V
	cost[r] = 0
	for _ in range(V - 1):
		for edge in edges:
			s = edge[0]
			t = edge[1]
			d = edge[2]
			if cost[t] < cost[s] + d:
				cost[t] = cost[s] + d
	ans = cost[V - 1]
	for _ in range(V - 1):
		for edge in edges:
			s = edge[0]
			t = edge[1]
			d = edge[2]
			if cost[t] < cost[s] + d:
				cost[t] = cost[s] + d
	if ans != cost[V - 1]:
		return float('inf')
	return ans
(V, E) = map(int, input().split())
edges = []
for _ in range(E):
	(s, t, d) = map(int, input().split())
	s -= 1
	t -= 1
	edges.append(tuple((s, t, d)))
ans = solve(V, E, 0, edges)
if ans == float('inf'):
	print('inf')
else:
	print(ans)


(N, M) = map(int, input().split())
gra = [[] for i in range(N)]
p = [[0] + [-float('inf')] * (N - 1) for i in range(N * 2 + 1)]
p[0][0] = 0
for i in range(M):
	(a, b, c) = map(int, input().split())
	gra[a - 1].append([b - 1, c])
for i in range(N * 2):
	for j in range(N):
		for (b, c) in gra[j]:
			p[i + 1][b] = max(p[i + 1][b], p[i][j] + c, p[i][b])
print(['inf', p[N][-1]][p[N][-1] == p[-1][-1]])


import sys
(N, M) = map(int, input().split())
es = []
for _ in range(M):
	e = list(map(int, input().split()))
	e[2] *= -1
	es.append(e)
INF = float('inf')
d = [INF for _ in range(N + 1)]
d[1] = 0
negative = [0 for _ in range(N + 1)]
for i in range(N):
	for j in range(M):
		e = es[j]
		if d[e[1]] > d[e[0]] + e[2]:
			d[e[1]] = d[e[0]] + e[2]
			if i == N - 1:
				negative[e[0]] = 1
				negative[e[1]] = 1
for i in range(M):
	e = es[i]
	if negative[e[0]]:
		negative[e[1]] = 1
if negative[N]:
	print('inf')
else:
	print(-d[N])


def abc061_d():
	(n, m) = map(int, input().split())
	edges = [tuple(map(int, input().split())) for _ in range(m)]
	inf = float('inf')
	result = [inf] * n
	result[0] = 0
	for i in range(n - 1):
		for (f, t, c) in edges:
			result[t - 1] = min(result[t - 1], result[f - 1] - c)
	ans = result[n - 1]
	for (f, t, c) in edges:
		result[t - 1] = min(result[t - 1], result[f - 1] - c)
	print(-ans if ans == result[n - 1] else 'inf')
abc061_d()


import sys
from copy import deepcopy
(n, m) = [int(i) for i in input().split()]
es = [[int(j) for j in input().split()] for i in range(m)]
x = [float('-inf')] * (n + 1)
x[1] = 0
border = sys.maxsize // 1000
for i in range(n):
	for (a, b, c) in es:
		x[b] = max(x[b], x[a] + c)
		if x[b] >= border:
			x[b] = float('inf')
prevxn = x[n]
for (a, b, c) in es:
	x[b] = max(x[b], x[a] + c)
if prevxn != x[n]:
	print('inf')
else:
	print(x[n])


(N, M) = map(int, input().split())
(a, b, c) = ([None] * M, [None] * M, [None] * M)
INF = 100000000000000.0
d = [-INF] * N
d[0] = 0
for i in range(M):
	(a[i], b[i], c[i]) = 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)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
edges = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	edges.append((a, b, -c))
dist = [float('inf')] * (N + 1)
dist[1] = 0
for _ in range(N - 1):
	for (u, v, weight) in edges:
		if dist[v] > dist[u] + weight:
			dist[v] = dist[u] + weight
negative = [False] * (N + 1)
for _ in range(N):
	for (u, v, weight) in edges:
		if dist[v] > dist[u] + weight:
			dist[v] = dist[u] + weight
			negative[v] = True
print('inf' if negative[N] else -dist[N])


(N, M) = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(M)]
INF = -10 ** 20
d = [INF for _ in range(N)]
d[0] = 0
for i in range(2 * N):
	f = True
	rel = d[-1]
	for j in range(M):
		(a, b, c) = abc[j]
		a -= 1
		b -= 1
		if d[b] < d[a] + c:
			d[b] = d[a] + c
			f = False
	if f:
		break
else:
	if rel != d[-1]:
		print('inf')
		exit()
print(d[-1])


(N, M) = map(int, input().split())
edge = [0] * M
for i in range(M):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c *= -1
	edge[i] = (a, b, c)
inf = float('inf')
V = N
E = M
d = [inf] * V
d[0] = 0
for i in range(V):
	for j in range(E):
		(From, To, cost) = edge[j]
		if d[From] != inf and d[To] > d[From] + cost:
			d[To] = d[From] + cost
ans = d[N - 1]
for i in range(V):
	for j in range(E):
		(From, To, cost) = edge[j]
		if d[From] != inf and d[To] > d[From] + cost:
			d[To] = d[From] + cost
if d[N - 1] != ans:
	print('inf')
else:
	print(-ans)


from collections import deque
(N, M) = map(int, input().split())
ABC = []
Adake = [[] for _ in range(N)]
Bdake = [[] for _ in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	ABC.append((a - 1, b - 1, -c))
	Adake[a - 1].append(b - 1)
	Bdake[b - 1].append(a - 1)

def dfs(X, s):
	used = {s}
	search = deque([s])
	while search:
		ss = search.pop()
		for sss in X[ss]:
			if sss in used:
				continue
			used.add(sss)
			search.append(sss)
	return used
U = dfs(Adake, 0) & dfs(Bdake, N - 1)
ABC = [(a, b, c) for (a, b, c) in ABC if a in U and b in U]
INF = float('inf')
dist = [INF] * N
dist[0] = 0
for i in range(N):
	for (a, b, c) in ABC:
		if dist[b] > dist[a] + c:
			dist[b] = dist[a] + c
			if i == N - 1 and b == N - 1:
				print('inf')
				return
print(-dist[-1])


(n, m) = map(int, input().split())
from collections import defaultdict
G = defaultdict(dict)
for i in range(1, n):
	G[i + 1] = {}
for i in range(m):
	(a, b, c) = map(int, input().split())
	G[a][b] = c
start_vertex = 1

def bellmanford(G, start_vertex):
	if start_vertex not in G:
		return (-1, -1)
	distances = {}
	parents = {}
	for node in G:
		distances[node] = float('-inf')
		parents[node] = None
	distances[start_vertex] = 0
	for _ in range(len(G) - 1):
		for node in G.keys():
			for neighbor in G[node]:
				if distances[neighbor] < distances[node] + G[node][neighbor]:
					distances[neighbor] = distances[node] + G[node][neighbor]
					parents[neighbor] = node
	pathnode = n
	while pathnode != start_vertex:
		for neighbor in G[pathnode]:
			if distances[neighbor] < distances[pathnode] + G[pathnode][neighbor]:
				print('inf', flush=True)
				return (-1, -1)
		pathnode = parents[pathnode]
	return (distances, parents)
(distances, parents) = bellmanford(G, start_vertex)
if distances != -1:
	print(distances[n], flush=True)


(n, m) = map(int, input().split())
edges = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	edges.append((a, b, -c))
init_v = 0
INF = float('inf')
dist = [INF] * n
dist[init_v] = 0
negative_cycle = 0
for i in range(2 * n):
	for (v, v2, c) in edges:
		if dist[v2] <= dist[v] + c:
			continue
		dist[v2] = dist[v] + c
		if i >= n - 1 and v2 == n - 1:
			negative_cycle = 1
if negative_cycle:
	print('inf')
else:
	print(-dist[-1])


(n, m) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
distance = [float('inf')] * n
distance[0] = 0
for i in range(n - 1):
	for j in range(m):
		if distance[l[j][1] - 1] > distance[l[j][0] - 1] - l[j][2]:
			distance[l[j][1] - 1] = distance[l[j][0] - 1] - l[j][2]
x = distance[n - 1]
for i in range(n):
	for j in range(m):
		if distance[l[j][1] - 1] > distance[l[j][0] - 1] - l[j][2]:
			distance[l[j][1] - 1] = -float('inf')
if distance[n - 1] == x:
	print(-distance[n - 1])
else:
	print('inf')


from scipy.sparse.csgraph import connected_components, bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix
(N, M) = list(map(int, input().split()))
(frm, to, length) = ([], [], [])
for _ in range(M):
	(a, b, c) = list(map(int, input().split()))
	frm.append(a - 1)
	to.append(b - 1)
	length.append(-c)
connect_check = csr_matrix(([1] * (M + 1), (frm + [N - 1], to + [0])), shape=(N, N))
(_, labels) = connected_components(connect_check, connection='strong')
label_num = labels[0]
(frm_c, to_c, length_c) = ([], [], [])
for i in range(M):
	if labels[frm[i]] == labels[to[i]] == label_num:
		frm_c.append(frm[i])
		to_c.append(to[i])
		length_c.append(length[i])
matr = csr_matrix((length_c, (frm_c, to_c)), shape=(N, N))
try:
	ans = -int(bellman_ford(matr, indices=0)[N - 1])
	print(ans)
except NegativeCycleError:
	print('inf')


import sys

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

def bellman_ford(edges, N, start):
	dist = [float('inf') for _ in range(N)]
	dist[start] = 0
	for i in range(2 * N):
		for (fro, to, cost) in edges:
			if dist[to] > dist[fro] - cost:
				dist[to] = dist[fro] - cost
				if i == N - 1:
					dist[to] = -float('inf')
	return dist

def main():
	(N, M) = list(map(int, input().split()))
	edge = []
	for i in range(M):
		(a, b, c) = list(map(int, input().split()))
		edge.append((a - 1, b - 1, c))
	D = bellman_ford(edge, N, 0)
	print(-1 * D[-1])

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(m)]
d = [-float('inf')] * (n + 1)
d[1] = 0
for _ in range(n):
	for (i, j, c) in e:
		d[j] = max(d[j], d[i] + c)
t = d[n]
for _ in range(n):
	for (i, j, c) in e:
		d[j] = max(d[j], d[i] + c)
if t < d[n]:
	print('inf')
else:
	print(d[n])


(n, m) = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(m)]
v = [-(10 ** 9 * 2000)] * n
v[0] = 0
for i in range(n):
	tmp = v[-1]
	for (a, b, cost) in e:
		if v[a - 1] + cost > v[b - 1]:
			v[b - 1] = v[a - 1] + cost
	if tmp != v[-1] and i == n - 1:
		break
else:
	print(v[n - 1])
	exit()
print('inf')


(N, M) = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
dp = [-1 * float('INF')] * (N + 1)
dp[1] = 0
for _ in range(N - 1):
	for (a, b, c) in edges:
		dp[b] = max(dp[b], dp[a] + c)
tmp1 = dp[N]
for _ in range(N - 1):
	for (a, b, c) in edges:
		dp[b] = max(dp[b], dp[a] + c)
tmp2 = dp[N]
if tmp2 > tmp1:
	print('inf')
else:
	print(tmp1)


(n, m) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
distance = [9999999999999999] * n
distance[0] = 0
for i in range(n - 1):
	for j in range(m):
		if distance[l[j][1] - 1] > distance[l[j][0] - 1] - l[j][2]:
			distance[l[j][1] - 1] = distance[l[j][0] - 1] - l[j][2]
f = [0] * n
for i in range(n):
	for j in range(m):
		if distance[l[j][1] - 1] > distance[l[j][0] - 1] - l[j][2]:
			distance[l[j][1] - 1] = distance[l[j][0] - 1] - l[j][2]
			f[l[j][1] - 1] = 1
		if f[l[j][0] - 1] == 1:
			f[l[j][1] - 1] = 1
if f[n - 1] == 0:
	print(-distance[n - 1])
else:
	print('inf')


def find_negative_loop(n, es, d):
	check = [0 for _ in range(n)]
	for _ in range(n):
		for (p, q, r) in es:
			if d[p] != float('inf') and d[q] > d[p] + r:
				d[q] = d[p] + r
				check[q] = True
			if check[p]:
				check[q] = True
	return check

def shortest_path(s, n, es):
	d = [float('inf')] * n
	d[s] = 0
	for _ in range(n):
		update = False
		for (p, q, r) in es:
			if d[p] != float('inf') and d[q] > d[p] + r:
				d[q] = d[p] + r
				update = True
		if not update:
			break
	return d
(n, w) = map(int, input().split())
es = []
for _ in range(w):
	(x, y, z) = map(int, input().split())
	es.append([x - 1, y - 1, -z])
d = shortest_path(0, n, es)
c = find_negative_loop(n, es, d)
if c[-1]:
	print('inf')
else:
	print(-d[-1])


(N, M) = map(int, input().split())
edges = []
E = [[] for _ in range(N)]
for _ in range(M):
	(fr, to, cost) = 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')
				return
			minDist[to] = d
print(-minDist[N - 1])


INF = float('inf')

class BellmanFord:

	def bellmanford(self, s, V, E):
		dist = [INF for _ in range(V)]
		dist[s] = 0
		for i in range(V):
			for e in E:
				(u, v, cost) = e
				if dist[u] != INF and dist[v] > dist[u] + cost:
					dist[v] = dist[u] + cost
					if i == V - 1 and v == V - 1:
						return -1
		return dist

def main():
	(N, M) = map(int, input().split())
	E = []
	for _ in range(M):
		(a, b, c) = map(int, input().split())
		a -= 1
		b -= 1
		E.append((a, b, -c))
	bf = BellmanFord()
	dist = bf.bellmanford(0, N, E)
	if dist == -1:
		print('inf')
	else:
		ans = dist[-1]
		print(-ans)

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 15

class edge:

	def __init__(self, fr, to, cost):
		(self.fr, self.to, self.cost) = (fr, to, cost)

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

def Z():
	return int(input())

def ZZ():
	return [int(_) for _ in input().split()]

def main():
	(N, M) = ZZ()
	es = []
	for _ in range(M):
		(a, b, c) = ZZ()
		a -= 1
		b -= 1
		es.append(edge(a, b, -c))
	d = [0] * N
	for i in range(N):
		for e in es:
			if d[e.to] > d[e.fr] + e.cost:
				d[e.to] = d[e.fr] + e.cost
				if e.to == N - 1 and i == N - 1:
					print('inf')
					return
	d = [INF] * N
	d[0] = 0
	for _ in range(N - 1):
		update = False
		for e in es:
			if d[e.fr] != INF and d[e.to] > d[e.fr] + e.cost:
				d[e.to] = d[e.fr] + e.cost
				update = True
		if not update:
			break
	print(-d[N - 1])
	return

def __starting_point():
	main()
__starting_point()


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

def BellmanFord(edges, num_v, s):
	inf = float('inf')
	dist = [inf] * num_v
	dist[s] = 0
	for i in range(num_v):
		for edge in edges:
			if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
				dist[edge[1]] = dist[edge[0]] + edge[2]
				if i == num_v - 1 and edge[1] == num_v - 1:
					return -1
	return dist[num_v - 1]
edges = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	c *= -1
	edges.append((a, b, c))
if BellmanFord(edges, n, 0) == -1:
	print('inf')
else:
	print(-BellmanFord(edges, n, 0))


def main():
	INF = float('inf')
	(N, M) = map(int, input().split())
	dist = [0] + [INF] * (N - 1)
	abc = []
	for i in range(M):
		(a, b, c) = map(int, input().split())
		abc.append((a - 1, b - 1, -c))
	for (a, b, c) in abc:
		dist[b] = min(dist[b], dist[a] + c)
	ans = dist[-1]
	for (a, b, c) in abc:
		dist[b] = min(dist[b], dist[a] + c)
	if ans != dist[-1]:
		print('inf')
	else:
		print(-ans)
main()


(n, m) = map(int, input().split())
edge_list = []
for _ in range(m):
	(a_i, b_i, c_i) = map(int, input().split())
	edge_list.append((a_i - 1, b_i - 1, -c_i))
INF = 10 ** 15
cost = [INF] * n
cost[0] = 0
NegativeLoopExist = False
for i in range(n):
	for j in range(m):
		(a, b, c) = edge_list[j]
		if cost[a] != INF and cost[b] > cost[a] + c:
			cost[b] = cost[a] + c
			if i == n - 1 and b == n - 1:
				NegativeLoopExist = True
if NegativeLoopExist:
	print('inf')
else:
	print(-cost[n - 1])


def BellmanFord():

	def BF(s, n, edge, inf=float('inf')):
		d = [inf for i in range(n)]
		d[s] = 0
		for i in range(n):
			for (before, after, dist) in edge:
				if before != inf:
					d[after] = min(d[after], d[before] + dist)
			if i == n - 2:
				t = d[:]
			elif i == n - 1:
				for (i, j) in enumerate(d):
					if j != t[i]:
						d[i] = -inf
		return list(map(lambda x: -x, d))
	(n, m) = map(int, input().split())
	inf = 10 ** 20
	edge = [list(map(int, input().split())) for i in range(m)]
	edge = [[x - 1, y - 1, -z] for (x, y, z) in edge]
	l = BF(0, n, edge)
	print(l[-1] if l[-1] < inf else 'inf')
BellmanFord()


import sys
(N, M) = map(int, input().split())
abc = [[] for _ in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	abc[a - 1].append((b - 1, c))
S = [-float('inf')] * N
S[0] = 0
T = [0]
m = 0
n = 0
j = False
while T:
	t = T.pop(0)
	m += 1
	for (tb, tc) in abc[t]:
		if S[tb] < S[t] + tc:
			S[tb] = S[t] + tc
			T.append(tb)
	if m > M + 1:
		d = abc[tb]
		if N - 1 in list((d[i][0] for i in range(len(d)))):
			j = True
		n += 1
	if n > M:
		if j:
			print('inf')
			return
		else:
			break
print(S[-1])


(N, M) = map(int, input().split())
routes = list()
for i in range(M):
	routes.append(list(map(int, input().split())))
score = [0, 0] + [10 ** 13] * (N - 1)
negative = [False] * (N + 1)
for i in range(N - 1):
	for (a, b, c) in routes:
		if score[b] > score[a] - c:
			score[b] = score[a] - c
ans = -score[N]
for i in range(N):
	for (a, b, c) in routes:
		if score[b] > score[a] - c:
			score[b] = score[a] - c
			negative[b] = True
		if negative[a] == True:
			negative[b] = True
if negative[N] == True:
	print('inf')
else:
	print(ans)


(n, m) = map(int, input().split())
edge = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	edge.append([a, b, -c])
check = [False for i in range(n + 1)]
inf = False
node = [float('inf') for i in range(n + 1)]
node[1] = 0
for i in range(n - 1):
	for (s, e, c) in edge:
		if node[e] > node[s] + c:
			node[e] = node[s] + c
for i in range(n):
	for (s, e, c) in edge:
		if node[e] > node[s] + c:
			node[e] = node[s] + c
			check[e] = True
		if check[s]:
			check[e] = True
if check[-1]:
	print('inf')
else:
	print(-node[-1])


import sys

def input():
	return sys.stdin.readline().strip()
(N, M) = list(map(int, input().split()))
edge = []
for _ in range(M):
	edge.append(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])


(N, M) = map(int, input().split())
(a, b, c) = ([0] * M, [0] * M, [0] * M)
d = [-1e+20] * N
for i in range(M):
	(a[i], b[i], c[i]) = 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])


import heapq
(N, M) = map(int, input().split())
E = [[] for i in range(N)]
for i in range(M):
	(a, b, c) = map(int, input().split())
	E[a - 1].append([b - 1, -c])
D = [N * 10 ** 9 + 1] * N
D[0] = 0

def bf(D):
	for i in range(N):
		_D = [d for d in D]
		for s in range(N):
			for adj in E[s]:
				_D[adj[0]] = min(D[s] + adj[1], _D[adj[0]])
		D = _D
	return D
D = bf(D)
d1 = D[-1]
D = bf(D)
print(-d1 if d1 == D[-1] else 'inf')


(N, M) = map(int, input().split())
edge = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	edge.append([a, b, c * -1])
d = [float('inf')] * (N + 1)
d[1] = 0
for i in range(1, N + 1):
	for e in edge:
		if (d[e[0]] != float('inf')) & (d[e[1]] > d[e[0]] + e[2]):
			d[e[1]] = d[e[0]] + e[2]
			update = True
			if (i == N) & (e[1] == N):
				print('inf')
				exit()
print(d[N] * -1)


(N, M) = map(int, input().split())
INF = 2 ** 63 - 1
d = [-1 * INF for i in range(N + 1)]
d[1] = 0
data = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	data.append([a, b, c])
for i in range(N):
	d_N = d[N]
	for j in range(M):
		a = data[j][0]
		b = data[j][1]
		c = data[j][2]
		d[b] = max(d[b], d[a] + c)
	if i == N - 1:
		if d_N != d[N]:
			ans = 'inf'
		else:
			ans = d[N]
print(ans)


(N, M) = [int(i) for i in input().split()]
G_ls = []
d = [-float('inf') for i in range(N)]
for i in range(M):
	(a, b, c) = [int(i) for i in input().split()]
	a -= 1
	b -= 1
	G_ls.append([a, b, c])

def update(x, y, is_updated):
	if x < y:
		is_updated = True
		x = y
	return (x, is_updated)
d[0] = 0
G_ls.sort(key=lambda x: x[0])
for i in range(N):
	for j in range(M):
		is_updated = False
		(a, b, c) = G_ls[j]
		(d[b], is_updated) = update(d[b], d[a] + c, is_updated)
if is_updated:
	print('inf')
else:
	print(d[-1])


(n, m) = list(map(int, input().split()))
graph = [float('INF') for i in range(n)]
graph[0] = 0
edge = [tuple(map(int, input().split())) for i in range(m)]
for i in range(2 * n):
	flag = False
	for e in edge:
		(a, b, c) = e
		(a, b, c) = (a - 1, b - 1, -c)
		if graph[b] > graph[a] + c:
			if b == n - 1:
				flag = True
			graph[b] = graph[a] + c
if flag:
	print('inf')
else:
	print(-graph[n - 1])


(n, m) = map(int, input().split())
abc = [list(map(int, input().split())) for _ in [0] * m]
g = [[] for _ in [0] * n]
[g[a - 1].append([b - 1, c]) for (a, b, c) in abc]
dist = [-10 ** 15 for _ in [0] * n]
dist[0] = 0
(a, b) = (-10 ** 15, -10 ** 15)
for _ in range(n):
	for p in range(n):
		for (i, j) in g[p]:
			dist[i] = max(dist[i], dist[p] + j)
	(a, b) = (b, dist[n - 1])
if a == b:
	print(a)
else:
	print('inf')


(N, M) = map(int, input().split())
E = [list(map(int, input().split())) for i in range(M)]
C = [-float('inf')] * (N + 1)
C[1] = 0
for i in range(N - 1):
	for e in E:
		(a, b, c) = e
		C[b] = max(C[b], C[a] + c)
ans = C[N]
for i in range(N):
	for e in E:
		(a, b, c) = e
		C[b] = max(C[b], C[a] + c)
if C[N] == ans:
	print(ans)
else:
	print('inf')


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

def bellman_ford(s):
	d = [float('inf')] * n
	d[s] = 0
	for i in range(n * 2):
		for edge in g:
			if edge[0] != float('inf') and d[edge[1]] > d[edge[0]] + edge[2]:
				d[edge[1]] = d[edge[0]] + edge[2]
				if i >= n - 1 and edge[1] == n - 1:
					return -1
	return d
g = []
for _ in range(m):
	(a, b, c) = list(map(int, input().split()))
	a -= 1
	b -= 1
	c *= -1
	g.append([a, b, c])
ret = bellman_ford(0)
if isinstance(ret, list):
	print(-1 * ret[n - 1])
else:
	print('inf')


(V, M) = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(M)]
G = [list() for i in range(V)]
for (a, b, c) in abc:
	G[b - 1].append((a - 1, -c))
INF = 10 ** 18
dist = [INF] * V
dist[V - 1] = 0
update = 1
for _ in range(V):
	update = 0
	for (v, e) in enumerate(G):
		for (t, cost) in e:
			if dist[v] != INF and dist[v] + cost < dist[t]:
				dist[t] = dist[v] + cost
				update = 1
	if not update:
		break
else:
	print('inf')
	exit()
print(-dist[0])


(N, M) = map(int, input().split())
edges = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	edges.append((a - 1, b - 1, c))
inf = float('inf')
dist = [-inf for i in range(N)]
dist[0] = 0
is_cycle = False
for i in range(N):
	for edge in edges:
		new_dist = dist[edge[0]] + edge[2]
		if dist[edge[1]] < new_dist:
			dist[edge[1]] = new_dist
			if i == N - 1 and edge[1] == N - 1:
				is_cycle = True
ans = dist[-1] if not is_cycle else 'inf'
print(ans)


import bisect
import collections
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 60

def lmi():
	return list(map(int, input().split()))

def llmi(n):
	return [lmi() for _ in range(n)]
(N, M) = lmi()
ABC = llmi(M)

class BellmanFord:

	def __init__(self, n, start=0):
		self.n = n
		self.cost = [INF] * n
		self.cost[start] = 0
		self.edge = dict()

	def add_edge(self, _from, _to, _cost):
		self.edge[_from, _to] = _cost

	def fill_cost(self, check=False):
		negative_loops = set()
		for i in range(self.n):
			for ((_from, _to), _cost) in list(self.edge.items()):
				if self.cost[_from] != INF and self.cost[_to] > self.cost[_from] + _cost:
					self.cost[_to] = self.cost[_from] + _cost
					if check:
						negative_loops.add(_to)
		return negative_loops
bf = BellmanFord(N)
for (a, b, c) in ABC:
	bf.add_edge(a - 1, b - 1, -c)
bf.fill_cost()
negative_loops = bf.fill_cost(check=True)
if N - 1 in negative_loops:
	print('inf')
else:
	print(-bf.cost[-1])


(N, M) = [int(_) for _ in input().split()]
T = [[int(_) for _ in input().split()] for i in range(M)]
E = []
for (a, b, c) in T:
	E.append((a - 1, b - 1, c))
min_V = -1000000000 * 2000
scores = [min_V] * N
scores[0] = 0
for i in range(N):
	for (a, b, c) in E:
		if scores[b] >= scores[a] + c:
			continue
		scores[b] = scores[a] + c
ans = scores[N - 1]
for (a, b, c) in E:
	if scores[b] >= scores[a] + c:
		continue
	scores[b] = scores[a] + c
if ans != scores[N - 1]:
	print('inf')
else:
	print(scores[N - 1])


(N, M) = map(int, input().split())
G = []
for _ in range(M):
	(a, b, c) = map(int, input().split())
	G.append((a, b, -c))
inf = float('inf')
d = [inf] * (N + 1)
d[1] = 0
for i in range(N + 1):
	for (v, nv, cost) in G:
		if d[v] != inf and d[nv] > d[v] + cost:
			d[nv] = d[v] + cost
			if i == N - 1:
				tmp = d[N]
			if i == N and d[N] != tmp:
				print('inf')
				exit()
print(-d[N])


(n, m) = map(int, input().split(' '))
piece = [0] * m
for i in range(m):
	piece[i] = tuple(map(int, input().split(' ')))
node = [0] + [float('inf')] * (n - 1)
for v in range(n - 1):
	for e in range(m):
		(a, b, c) = piece[e]
		if node[b - 1] > node[a - 1] - c:
			node[b - 1] = node[a - 1] - c
ans = node[n - 1]
for e in range(m):
	(a, b, c) = piece[e]
	if node[b - 1] > node[a - 1] - c:
		node[b - 1] = node[a - 1] - c
if ans != node[n - 1]:
	print('inf')
else:
	print(-ans)


(N, M) = map(int, input().split())
edge = [tuple(map(int, input().split())) for i in range(M)]
cost = [-float('inf')] * N
cost[0] = 0
for n in range(N - 1):
	for m in range(M):
		(a, b, c) = edge[m]
		cost[b - 1] = max(cost[b - 1], cost[a - 1] + c)
r = cost[-1]
for m in range(M):
	(a, b, c) = edge[m]
	cost[b - 1] = max(cost[b - 1], cost[a - 1] + c)
print(r if cost[-1] == r else 'inf')


(n, m) = map(int, input().split())
E = [list(map(int, input().split())) for i in range(m)]
INF = float('inf')
dist = [INF] * n
dist[0] = 0
for i in range(n):
	for (fr, to, cost) in E:
		(fr, to) = (fr - 1, to - 1)
		cost *= -1
		if dist[fr] != INF and dist[to] > dist[fr] + cost:
			dist[to] = dist[fr] + cost
			if i == n - 1 and to == n - 1:
				print('inf')
				exit(0)
print(-dist[-1])


(n, m) = map(int, input().split())
edge = []
for _ in range(m):
	(a, b, c) = map(int, input().split())
	edge.append([a - 1, b - 1, -c])
d = [float('inf') for _ in range(n)]
d[0] = 0
check = [0 for _ in range(n)]
for i in range(n):
	for (now, next, weight) in edge:
		if d[next] > d[now] + weight:
			d[next] = d[now] + weight
			if i == n - 1:
				check[next] = 1
		if i == n - 1:
			if check[now]:
				check[next] = 1
if check[-1]:
	print('inf')
else:
	print(-d[-1])


(n, m) = map(int, input().split())
edge = []
for i in range(m):
	(a, b, c) = map(int, input().split())
	edge.append((a - 1, b - 1, -c))
inf = 99999999999999999999
d = [inf for i in range(n)]
d[0] = 0
count = 0
while count < n + 1:
	count += 1
	if count == n:
		tmp = d[n - 1]
	update = False
	for i in range(m):
		(f, t, cost) = edge[i]
		if d[t] > d[f] + cost:
			d[t] = d[f] + cost
			update = True
	if count == n and tmp != d[n - 1]:
		print('inf')
		break
	if not update:
		print(-d[n - 1])
		break
else:
	print(-d[n - 1])


(N, M) = map(int, input().split())
edges = []
for i in range(M):
	(a, b, c) = map(int, input().split())
	edges.append([a, b, -c])

def bellman_ford(edges, N):
	dist = [float('inf') for i in range(N)]
	dist[0] = 0
	for i in range(N - 1):
		for edge in edges:
			if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
				dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
	negative = [False] * N
	for i in range(N):
		for edge in edges:
			if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
				dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
				negative[edge[1] - 1] = True
			if negative[edge[0] - 1] == True:
				negative[edge[1] - 1] = True
	return 'inf' if negative[-1] else -dist[-1]
print(bellman_ford(edges, N))


def bellman_ford(edges, N, start, end):
	cost = [float('inf') for _ in range(N)]
	cost[start] = 0
	negative = [False for _ in range(N)]
	for i in range(N):
		for j in range(len(edges)):
			(fro, to, c) = edges[j]
			if cost[to] > cost[fro] + c:
				cost[to] = cost[fro] + c
				if i == N - 1:
					negative[to] = True
	if negative[end]:
		return 'inf'
	else:
		return -cost[end]
(N, M) = list(map(int, input().split()))
edges = []
for _ in range(M):
	(a, b, c) = list(map(int, input().split()))
	edges.append((a - 1, b - 1, -c))
cost = [float('inf') for _ in range(N)]
start = 0
end = N - 1
print(bellman_ford(edges, N, start, end))


(N, M) = list(map(int, input().split()))
a = []
b = []
c = []
for o in range(M):
	(a_i, b_i, c_i) = list(map(int, input().split()))
	a.append(a_i)
	b.append(b_i)
	c.append(c_i)
cost = [-float('inf') for i in range(N + 1)]
cost[1] = 0
flag = True
for _ in range(N - 1):
	for k in range(M):
		cost[b[k]] = max(cost[b[k]], cost[a[k]] + c[k])
cost_n = cost[N]

def check():
	for l in range(M):
		cost[b[l]] = max(cost[b[l]], cost[a[l]] + c[l])
	if cost[N] > cost_n:
		return 'inf'
	return cost[N]
print(check())