Problem:
 Score : 400 points    Problem Statement 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 1 3 3
1 2 4
2 3 3
1 3 5      Sample Output 1 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 .       Sample Input 2 2 2
1 2 1
2 1 1      Sample Output 2 inf  It is possible to increase the score indefinitely by alternating between vertex 1 and 2 .       Sample Input 3 6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000      Sample Output 3 -5000000000

Solution (Python):
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]

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

for _ in range(N-1):
    for a,b,c in abc:
        if dist[a] == float('inf'):
            continue
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c

ans = dist[N-1]
negative = [False]*N

for _ in range(N):
    for a,b,c in abc:
        if dist[a] == float('inf'):
            continue
        if dist[b] > dist[a] + c:
            dist[b] = dist[a] + c
            negative[b] = True
        if negative[a]:
            negative[b] = True

if negative[N-1]:
    print('inf')
else:
    print(-ans)

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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(-dist[N-1])

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
n, m =map(int, input().split())
INF = 10**15

a, b, c = [([0]*m) for _ in range(3)] 
for i in range(m):
    d,e,f = map(int, input().split())
    a[i] = d-1
    b[i] = e-1
    c[i] = -f

d = [INF]*n
d[0] = 0

for _ in range(n-1):
    for x,y,z in zip(a,b,c):
        if d[x] == INF:
            continue
        d[y] = min(d[y], d[x]+z)

ans = -d[-1]
negative = [False]*n

for _ in range(n):
    for x,y,z in zip(a,b,c):
        if d[x] == INF:
            continue
        if d[y] > d[x]+z:
            d[y] = d[x]+z
            negative[y] = True
        negative[y] |= negative[x]

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

Solution (Python):
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])

Solution (Python):
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))
point = [None] * N
point[0] = 0
for i in range((N*4)//3):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
current_point = point[N-1]
for i in range(5):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
if current_point < point[N-1]:
    print("inf")
else:
    print(current_point)

Solution (Python):
import heapq
from collections import defaultdict

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

def Bellman_Ford(s):
  d[s]=0
  for i in range(N-1):
    update=False
    for ft,c in V.items():
      frm,to=ft
      if d[frm]!=float('inf') and d[to]>d[frm]+c:
        d[to]=d[frm]+c
        update=True
    if not(update):
      break
  
def Bellma_Ford_rep(n):
  upd=[False for x in range(N)]
  for i in range(N):
    update=False
    for ft,c in V.items():
      frm,to=ft
      if d[to]>d[frm]+c or upd[frm]:
        update=True
        upd[to]=True
    if not(update):
      break
  return upd[n]

Bellman_Ford(0)
if Bellma_Ford_rep(N-1):
  print("inf")
else:
  print(-d[N-1])

Solution (Python):

inf = 10**50

N, M = map(int, input().split())
edges = []
for j in range(M):
    edges.append(list(map(int, input().split())))

d = [0] + ([-inf]*(N-1))
pred = [None] * N

for i in range(N-1):
    for j in range(M):
        u = edges[j][0]-1
        v = edges[j][1]-1
        w = edges[j][2]
        if (d[v] < d[u] + w) and (d[u] != -inf):
            d[v] = d[u] + w
            pred[v] = u

positive_loop = False
for i in range(N):
    for j in range(M):
        u = edges[j][0]-1
        v = edges[j][1]-1
        w = edges[j][2]
        if (d[u] + w > d[v]) and (d[u] != -inf):
            d[v] = d[u] + w
            if v == N-1:
                positive_loop = True
                break
    if positive_loop:
        break

if positive_loop:
    print("inf")
else:
    print(d[N-1])

Solution (Python):

inf = 10**50

N, M = map(int, input().split())
edges = []
for j in range(M):
    edges.append(list(map(int, input().split())))

d = [0] + ([-inf]*(N-1))
pred = [None] * N

for i in range(N-1):
    for j in range(M):
        u = edges[j][0]-1
        v = edges[j][1]-1
        w = edges[j][2]
        if (d[v] < d[u] + w) and (d[u] != -inf):
            d[v] = d[u] + w
            pred[v] = u

positive_loop = False
for i in range(N):
    for j in range(M):
        u = edges[j][0]-1
        v = edges[j][1]-1
        w = edges[j][2]
        if (d[u] + w > d[v]) and (d[u] != -inf):
            d[v] = d[u] + w
            if v == N-1:
                positive_loop = True
                break
    if positive_loop:
        break

if positive_loop:
    print("inf")
else:
    print(d[N-1])

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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 = deepcopy(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])

Solution (Python):
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])

Solution (Python):
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)

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])

Solution (Python):
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])

Solution (Python):
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())

Solution (Python):
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])

Solution (Python):

def inpl(): return tuple(map(int, input().split()))
INF = float("inf")
V, E = inpl()
 
edges = [inpl() for _ in range(E)]
 
def belman_ford(V, edges, r):
    "If glaph contains negative cycles then return True"
    D = [-INF]*(V+1)
    D[r] = 0


    
    for _ in range(V): 
        update = False
        for s, t, d in edges:
            if D[t] < D[s] + d:
                D[t] = D[s] + d
                update = True
        if not update:
            break
    else:
        NEGs = [False]*(V+1)
        for s, t, d in edges:
            if D[t] < D[s] + d:
                D[t] = D[s] + d
                NEGs[t] = True
                NEGs[s] = True
        return True, D, NEGs
                
    return False, D, [False]*(V+1)
  
isNEGATIVE, D, NEGs = belman_ford(V, edges, 1)
 
"""
3 = 4 < 1 > 5 なら閉路があっても問題なし 
"""   
if NEGs[-1]:
    print("inf")
else:
    print(D[-1])

Solution (Python):
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)

Solution (Python):
N, M = map(int, input().split())
a = [0 for i in range(M)]
b = [0 for i in range(M)]
c = [0 for i in range(M)]
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
distance = [-10**20 for i in range(N)]
distance[0] = 0
for i in range(1,N):
    for j in range(M):
        u = a[j]-1; v = b[j]-1
        if distance[v] < distance[u] + c[j]:
            distance[v] = distance[u] + c[j]
negative = [False for i in range(N)]
for i in range(N):
    for j in range(M):
        u = a[j]-1; v = b[j]-1
        if distance[v] < distance[u] + c[j]:
            distance[v] = distance[u] + c[j]
            negative[v] = True
        if negative[u]:
            negative[v] = True
if negative[N-1]:
    print("inf")
else:
    print(distance[N-1])

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

Solution (Python):
def d_ScoreAttack(N, M, R):
    INF = float('inf')
    
    dist = [INF] * N
    dist[0] = 0
    
    for i in range(N):
        for a, b, cost in R:
            u, v, c = a - 1, b - 1, -cost
            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]

N,M = [int(i) for i in input().split()]
R = [[int(i) for i in input().split()] for j in range(M)]
print(d_ScoreAttack(N, M, R))

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

Solution (Python):
N, M = map(int, input().split())
a, b, c = [0] * M, [0] * M, [0] * M
INF = int(1e13) + 1
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

d = [-INF] * N
d[0] = 0
for __x in range(N-1):
    for i in range(M):
        if d[b[i]] < d[a[i]] + c[i]:
            d[b[i]] = d[a[i]] + c[i]

isCycle = False
for __x in range(N-1):
    if isCycle:
        break
    for i in range(M):
        if d[b[i]] < d[a[i]] + c[i]:
            d[b[i]] = d[a[i]] + c[i]
            if b[i] == N-1:
                isCycle = True
                break

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

Solution (Python):
import sys
N,M=map(int,raw_input().split())
a=[]
for i in range(M):
	x,y,z=map(int,raw_input().split())
	a.append((x,y,-1*z))




x=[ float("inf") for _ in range(N+1)]

x[1]=0



for h in range(N):
	for fr,to,cost in a:
		x[to]=min(x[to],x[fr]+cost)



for h in range(N):
	for fr,to,cost in a:
		if x[to]>x[fr]+cost:
			x[to]=min(x[to],x[fr]+cost)			
			if to==N:
				print "inf"
				sys.exit()
			
print -1*x[N]

Solution (Python):


inf = float('inf')

def bellman_ford():
    for i in range(N):
        d[i] = inf
    d[0] = 0
    for i in range(N):
        for j in range(M):
            s, t, c = es[j]
            if d[s] != inf and d[t] > d[s] + c:
                d[t] = d[s] + c
    return -d[N - 1]


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

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

d = [0] * N
ans = bellman_ford()
negative = [False] * N
for i in range(N):
    for j in range(M):
        s, t, c = es[j]
        if d[s] != inf and d[t] > d[s] + c or negative[s]:
            negative[t] = True

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

Solution (Python):
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])

Solution (Python):
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')

Solution (Python):
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())

Solution (Python):
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 -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)

Solution (Python):
import sys 

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

for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
    c_list.append(-c)

inf = sys.maxsize
dist = [inf] * N
dist[0] = 0

for loop in range(N):
    for i in range(M):
        if dist[a_list[i]-1] == inf:
            continue
        if dist[b_list[i]-1] > dist[a_list[i]-1] + c_list[i]:
            dist[b_list[i]-1] = dist[a_list[i]-1] + c_list[i]
            if loop == N - 1 and b_list[i] == N:
                print('inf')
                sys.exit()

print(-dist[N-1])

Solution (Python):
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))

Solution (Python):
from collections import defaultdict
from itertools import count



def bellman_ford(edges, start_node, node_size):
    INF = float("inf")
    cost_table = [INF] * node_size
    cost_table[start_node] = 0
    for i in range(node_size):
        for f, t, c in edges:
            if cost_table[f] != INF and cost_table[f] + c < cost_table[t]:
                cost_table[t] = cost_table[f] + c

    negative = [False] * node_size
    for i in range(node_size):
        for f, t, c in edges:
            if cost_table[f] != INF and cost_table[f] + c < cost_table[t]:
                cost_table[t] = cost_table[f] + c
                negative[t] = True

            if negative[f]:
                negative[t] = True

    if negative[-1]:
        return "inf"
    else:
        return -cost_table[-1]



def main():
    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))


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

inf = 10 ** 20


def solve(n, m, weights):
    score = [-inf] * n
    score[0] = 0
    pred = [-1] * n

    for step 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

    b = n - 1
    while b != 0:
        a = pred[b]
        c = weights[(a, b)]
        if score[b] < score[a] + c:
            return 'inf'
        b = a
    return score[n-1]


def solve2(n, m, weights):
    score = [-inf] * n
    score[0] = 0
    pred = [-1] * n

    for step 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]

    for step 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

    if res < score[n-1]:
        return 'inf'
    return res


def main():
    n, m = map(int, input().split())
    weights = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        weights[(a, b)] = c

    res = solve2(n, m, weights)
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import sys



inf = 10 ** 20


def solve(n, m, weights):
    score = [-inf] * n
    score[0] = 0
    pred = [-1] * n

    for step 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

    b = n - 1
    while b != 0:
        a = pred[b]
        c = weights[(a, b)]
        if score[b] < score[a] + c:
            return 'inf'
        b = a
    return score[n-1]


def solve2(n, m, weights):
    score = [-inf] * n
    score[0] = 0
    pred = [-1] * n

    for step 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]

    for step 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

    if res < score[n-1]:
        return 'inf'
    return res


def main():
    n, m = map(int, input().split())
    weights = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        weights[(a, b)] = c

    res = solve(n, m, weights)
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000)

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

NINF = float('-inf')
dists = [NINF for _ in range(n)]
dists[0] = 0


def trace(v, updated):
    updated[v] = True
    for b, c in edges[v]:
        if not updated[b]:
            trace(b, updated)


def bellman_ford():
    for i in range(n - 1):
        updated = False
        for j in range(n):
            dj = dists[j]
            if dj == NINF:
                continue
            for b, c in edges[j]:
                if dists[b] >= dj + c:
                    continue
                dists[b] = dj + c
                updated = True
        if not updated:
            return dists[-1]

    n_updated = [False] * n
    for j in range(n):
        if n_updated[j]:
            continue
        dj = dists[j]
        if dj == NINF:
            continue
        for b, c in edges[j]:
            if dists[b] < dj + c:
                trace(b, n_updated)

    return 'inf' if n_updated[-1] else dists[-1]


print(bellman_ford())

Solution (Python):
n, m = map(int, input().split())
abc = [list(map(int, input().split())) for x in range(m)]
nodes = [[] for x in range(n + 1)]

for a, b, c in abc:
    nodes[a].append([a, b, -c])

costs = [None for x in range(n + 1)]
costs[1] = 0
flg = True
for i in range(n):
    for a, b, c in abc:
        if costs[a] == None:
            continue
        if costs[b] == None or costs[b] < costs[a] + c:
            flg = False
            costs[b] = costs[a] + c
    
    
    
    
    
    
    







ans = costs[n]
negative = [False for x in range(n + 1)]
for i in range(n - 1):
    for a, b, c in abc:
        if costs[a] == None:
            continue
        if costs[b] == None or costs[b] < costs[a] + c:
            costs[b] = costs[a] + c
            negative[b] = True

        if negative[a] == True:
            negative[b] = True

print(negative[n] and "inf" or ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)

inf = 1<<60

def solve():
    N, M = map(int, sys.stdin.readline().split())
    edges = [None] * M
    Adj = [[] for i in range(N)]

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

    reachable = [False] * N
    reachable[N - 1] = True
    dfs(N, Adj, reachable, N - 1)

    edges = [(ai, bi, ci) for (ai, bi, ci) in edges if reachable[ai] and reachable[bi]]

    ans = BellmanFord(N, M, edges)

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

    pass

def dfs(N, Adj, visited, u):
    for v in Adj[u]:
        if not visited[v]:
            visited[v] = True
            dfs(N, Adj, visited, v)

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

    for i in range(N - 1):
        for (ai, bi, ci) in edges:
            if d[ai] != inf and d[ai] + ci < d[bi]:
                d[bi] = d[ai] + ci

    for (ai, bi, ci) in edges:
        if d[ai] != inf and d[ai] + ci < d[bi]:
            return None

    return d[N - 1]

if __name__ == '__main__':
    solve()