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):
from heapq import *
N,M=map(int,input().split())
INF=float("inf")
G=[[] for i in range(N)]
Gm=[[] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    G[a].append((b,c))
    Gm[b].append((a,c))
O=[[0]*N for i in range(N)]
stack=[g for g in Gm[N-1]]
reached=[0]*N
reached[N-1]=1
while(stack):
    a,c=stack.pop()
    reached[a]=1
    for i,j in Gm[a]:
        if reached[i]==0:
            stack.append((i,j))
R=[False]*N
R[0]=0
stack=[(-i[1],0,i[0]) for i in G[0] if reached[i[0]]==1]
heapify(stack)
while(stack):
    c,a,b=heappop(stack)
    c=-c
    if R[b]==False:
        O[a][b]=1
        R[b]=c
        for i in G[b]:
            if reached[i[0]]==1:
                heappush(stack,(-i[1]-c,b,i[0]))
    if R[b]!=False and R[b]<c:
        if O[a][b]==1:
            print("inf")
            quit()
        else:
            R[b]=c
            O[a][b]=1
            for i in G[b]:
                if reached[i[0]]==1:
                    heappush(stack,(-i[1]-c,b,i[0]))

print(R[N-1])

Solution (Python):
INF = float("inf")
n, m = map(int, input().split())
edges = [None] * m





d = [INF] * n
d[0] = 0
def Bellmanford(n, e, s):

    
    for i in range(n):
        
        for a,b,c in e:
            
            if d[a] != INF and d[a] + c < d[b]:
                d[b] = d[a] + c

                
                if i == n-1 and b == n-1:
                    return INF


    return -1 * d[-1]



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)

Solution (Python):
N,M = map(int,input().split())

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

ABC = [[int(x) for x in input().split()] for _ in range(M)]
row,col,val = zip(*ABC)


val = [-x for x in val]








import numpy as np
from scipy.sparse.csgraph import connected_components

graph = csr_matrix((val,(row,col)),(N+1,N+1))

find_component_graph = csr_matrix(([1]*(M+1),(row+(N,),col+(1,))),(N+1,N+1))
_,labels = connected_components(find_component_graph,connection = 'strong')
idx = (labels == labels[1])


graph = graph[idx,:][:,idx]

try:
  dist = bellman_ford(graph,indices = [0])[0].astype(int)
  answer = -dist[-1]
except:
  answer = 'inf'

print(answer)

Solution (Python):
N,M = map(int,input().split())

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford

ABC = [[int(x) for x in input().split()] for _ in range(M)]
row,col,val = zip(*ABC)


val = [-x for x in val]








import numpy as np
from scipy.sparse.csgraph import connected_components

graph = csr_matrix((val,(row,col)),(N+1,N+1))

find_component_graph = csr_matrix(([1]*(M+1),(row+(N,),col+(1,))),(N+1,N+1))
_,labels = connected_components(find_component_graph,connection = 'strong')
idx = (labels == labels[1])

graph = graph[idx,:][:,idx]

try:
  dist = bellman_ford(graph,indices = [0])[0].astype(int)
  answer = -dist[-1]
except:
  answer = 'inf'

print(answer)

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

Solution (Python):
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float('inf')
from functools import reduce

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

dist = [inf]*n
dist[0] = 0
for i in range(1,n):
    for j in range(m):
        if dist[edge[j][1]] > dist[edge[j][0]]+edge[j][2]:
            dist[edge[j][1]] = dist[edge[j][0]]+edge[j][2]

ans = dist[n-1]

for j in range(m):
    if dist[edge[j][1]] > dist[edge[j][0]]+edge[j][2]:
        dist[edge[j][1]] = dist[edge[j][0]]+edge[j][2]
if dist[n-1]<ans:
    print("inf")
else:
    print(-ans)

Solution (Python):
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float('inf')
from functools import reduce

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

dist = [inf]*n
dist[0] = 0
for i in range(1,n):
    for j in range(m):
        if dist[edge[j][1]-1] > dist[edge[j][0]-1]+edge[j][2]:
            dist[edge[j][1]-1] = dist[edge[j][0]-1]+edge[j][2]

ans = dist[n-1]

for j in range(m):
    if dist[edge[j][1]-1] > dist[edge[j][0]-1]+edge[j][2]:
        dist[edge[j][1]-1] = dist[edge[j][0]-1]+edge[j][2]
if dist[n-1]<ans:
    print("inf")
else:
    print(-ans)

Solution (Python):
N, M = map(int, input().split())
a = [0]*M
b = [0]*M
c = [0]*M
for i in range(M):
	x, y, z = map(int, input().split())
	a[i] = x
	b[i] = y
	c[i] = -z

INF = float('inf')
d = [INF]*N
d[0] = 0

for _ in range(N-1):
	for i in range(M):
		if d[a[i]-1]==INF:
			continue
		if d[b[i]-1]>d[a[i]-1]+c[i]:
			d[b[i]-1] = d[a[i]-1] + c[i]

ans = -d[N-1]

negative = [False]*N
for _ in range(N):
	for i in range(M):
		if d[a[i]-1]==INF:
			continue
		if d[b[i]-1]>d[a[i]-1]+c[i]:
			d[b[i]-1] = d[a[i]-1] + c[i]
			negative[b[i]-1] = True
		if negative[a[i]-1]==True:
			negative[b[i]-1] = True

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

Solution (Python):
def bellmanford(v,e,s,path):
    inf = float('inf')
    d = [inf for i in range(v)]
    d[s] = 0
    for j in range(v):
        update = False
        for i in range(e):
            if d[path[i][0]] != inf and d[path[i][1]] > d[path[i][0]] + path[i][2]:
                d[path[i][1]] = d[path[i][0]] + path[i][2]
                update = True
                if j == v-1 and path[i][1]==n-1:
                    return -1
        if not update:
            break
    return d


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

path = []

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

d = bellmanford(n,m,0,path)

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

Solution (Python):
N, M = map(int, input().split())

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

edges = ABC[:]
NUM_V = N+1 


edges = [(a,b,-1*c) for a,b,c in edges]



import sys
INT_MAX = sys.maxsize 

def bellman_ford(edges,num_v,source):

    dist=[INT_MAX] * num_v
    dist[source]=0

    
    has_negative = False
    for i in range(num_v):
        for edge in edges:
            if edge[0] != INT_MAX and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i==num_v-1:
                    has_negative = True
    
    if has_negative == False:
        return dist
    
    negative = [False] * num_v
    for i in range(num_v):
        for from_edge, to_edge, cost in edges:
            if dist[from_edge] == INT_MAX:
                continue
            if dist[to_edge] > dist[from_edge] + cost:
                dist[to_edge] = dist[from_edge] + cost
                negative[to_edge] = True
            
            if negative[from_edge] == INT_MAX:
                negative[to_edge] = True
                
    for i, is_negative in enumerate(negative):
        if is_negative:
            dist[i] = -1 * INT_MAX
        
    return dist

longest = bellman_ford(edges, NUM_V, 1)
ans_value = -1 * longest[NUM_V - 1]
if ans_value == INT_MAX:
    print('inf')
else:
    print(ans_value)

Solution (Python):
N,M = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(M) ]
li = [ (a-1,b-1,c) for a,b,c in li ]

dw = [ [] for i in range(N) ]


for a,b,c in li:
  dw[a].append( (b,c) )

NOT = 1e+16 -1 
  
cost = [NOT]*N
cost[0]=0
cosli = []
for i in range(1000):
  chk = [0]*N
  now = 0
  pop=[now]
  for i in range(N):
    if (len(pop)==0):
      break
    now = pop.pop()
    chk[now]=1
    for b,c in dw[now]:
      if ( cost[b] == NOT ):
        cost[b] = cost[now] + c
      else:
        cost[b] = max(cost[now] + c,cost[b])
      if (chk[b]==0):
        pop.append(b)
  cosli.append( cost[N-1] )  

if ( cosli[-1] != cosli[-2] ):
  print ("inf")
else:
  print (cosli[-1])

Solution (Python):
from collections import deque


n, m = map(int, input().split())
tree = [[] for i in range(n)]
path = {}
for i in range(m):
    tmp1, tmp2, cost = map(int, input().split())
    tree[tmp1-1].append([tmp2-1, cost])

q = deque()
q.append([-1, 0])
pos_cost = [-float("inf")]*n
pos_cost[0] = 0
path = {}

def judge(start):
    q2 = deque()
    q2.append(start)
    visited = [False]*n
    visited[start] = True
    while q2:
        pos = q2.popleft()
        for next_pos, cost in tree[pos]:
            if not visited[next_pos]:
                q2.append(next_pos)
                visited[next_pos] = True
    if visited[n-1]:
        print("inf")
        exit()

while q:
    prev_pos, pos = q.popleft()
    if prev_pos*10000 + pos in path:
        judge(pos)
        continue
    path[prev_pos*10000 + pos] = 1
    for next_pos, cost in tree[pos]:
        if pos_cost[pos] + cost > pos_cost[next_pos]:
            pos_cost[next_pos] = pos_cost[pos] + cost
            q.append([pos, next_pos])
print(pos_cost[n-1])

Solution (Python):






inpPh = 3
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 

if inpPh > 0:
    pass
 
   


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), input().split() ) )
else:
    N,M = tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), input().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,-ci))

vlist =[ None for _ in range(N)]    

        
s_loc,g_loc = 0, N-1

vlist[s_loc] = 0





is_inf = False
for i in range(len(vlist)):
    for e in elist:
        a,b,c = e
        if vlist[a] == None:
            continue
        elif vlist[b] == None or vlist[b] > vlist[a] + c:
            vlist[b] = vlist[a] + c
            if i == N-1 and b == N-1:
                pass
                is_inf = True
                 
res = -vlist[g_loc]            


if is_inf:
    print('inf')
else:
    print(res)

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


from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford



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

rows = []
cols = []
weights = []

for _ in range(M):
    
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(-a)


graph = coo_matrix((weights, (cols, rows)), shape=(N, N)).tocsr() 
try:
    d1 = bellman_ford(graph, indices = [N-1], directed=True, unweighted=False)
    print(-int(d1[0][0]))
except:
    print("inf")

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math

mod = 10**9+7

N,M = map(int,input().split())
ways = []
for i in range(M):
    way = [int(i) for i in input().split()]
    ways.append(way)

ways.sort()
dp = [None for i in range(N+1)]

dp[1] = 0
cnt_way = 0
for j in range(N+1):
    for i in range(M):
        a,b,c = ways[i]
        if dp[a] != None:
            if dp[b] == None:
                dp[b] = dp[a] + c
            else:
                dp[b] = max(dp[b],dp[a]+c)

    if j == N-1:
        ans = dp[-1]

if ans == dp[-1]:
    pass
elif ans < dp[-1]:
    ans = "inf"

print(ans)

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

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

Solution (Python):

import sys

inf = float('inf')

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    V = list(range(N))
    
    next_v = [[] for v in V]
    for i in range(M):
        next_v[a[i]-1].append((b[i]-1, c[i]))
    
    D = [-inf for v in V]
    D[0] = 0
    
    prev = [None for v in V]

    positive = [False for v in V]

    for i in range(N-1):
        for u in V:
            for v, w in next_v[u]:
                alt = D[u] + w
                if alt > D[v]:
                    D[v] = alt
                    prev[v] = u
    ans = D[N-1]
    
    for i in range(N-1):
        for u in V:
            for v, w in next_v[u]:
                alt = D[u] + w
                if alt > D[v]:
                    D[v] = alt
                    positive[v] = True
                if positive[u]:
                    positive[v] = True

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



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    c = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

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

print(-dist[N - 1])

Solution (Python):
n, m = map(int,input().split())
edge = []
c = []
ed_list = [[] for _ in range(n)]
for i in range(m):
    t_a, t_b, t_c = map(int,input().split())
    edge.append([t_a - 1,  t_b - 1])
    c.append(-t_c)
    ed_list[t_a - 1].append(t_b - 1)

INF = float('inf')
score = [INF for _ in range(n)]
score[0] = 0
for i in range(n):
    for u, cost in zip(edge, c):
        if score[u[1]] > score[u[0]] + cost:
            score[u[1]] = score[u[0]] + cost
ans = score[n-1]
for i in range(n):
    for u, cost in zip(edge, c):
        if score[u[1]] > score[u[0]] + cost:
            score[u[1]] = score[u[0]] + cost
print(-ans if ans == score[n-1] else 'inf')

Solution (Python):
from collections import *
d=defaultdict(list)
n,m=map(int,input().split())
 
for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])


def BELLMANFORD(point,d):
    cost       = {node:-float("inf")for node in range(1,n+1)}
    preference = {node:None         for node in range(1,n+1)}      
    cost[point]= 0
    for i in range(n-1):                                  
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now

    negative=[0]*n                                        
    
    for i in range(n):                  
        for now,lis in d.copy().items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c:
                    cost[nex]=cost[now]+c
                    preference[nex]=now
                    negative[now-1]=1

    return cost,negative

x,y=(BELLMANFORD(1,d))

if y[n-1]==1:
    print("inf")
else:
    print(x[n])

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

Solution (Python):
from functools import reduce
import math

def main():
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N,M = (int(_) for _ in input().split())
    a = []
    b = []
    c = []
    d = [INF]*N
    
    for i in range(M):
        s1, s2, s3 = (int(_) for _ in input().split())
        a.append(s1)
        b.append(s2)
        c.append(-s3)
    d[0] = 0
    cnt = [0]*N
    for j in range(N):
        update=False
        for i in range(M):
            if math.isinf(d[a[i]-1]):
                continue
            if(d[b[i]-1] > d[a[i]-1]+c[i]):
                d[b[i]-1] = d[a[i]-1]+c[i]
                cnt[b[i]-1]+=1
                update=True
        if not update:
            break
    if cnt[N-1] < N:
        ans = -d[N-1]
    else:
        ans = 'inf'
    
    
    
    
    
    
    
    
    
    
    
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):

import sys
inf=10**15
fastinput=sys.stdin.readline
N,M=map(int,fastinput().split())
cost=[inf]*N
cost[0]=0
abc=[[int(o) for o in fastinput().split()] for _ in range(M)]
for t in range(N):
    changed=0
    for a,b,c in abc:
        if cost[b-1]>cost[a-1]-c:
            changed=1
            cost[b-1]=cost[a-1]-c
gendankainokosuto=cost[N-1]
for t in range(100):
    changed=0
    for a,b,c in abc:
        if cost[b-1]>cost[a-1]-c:
            changed=1
            cost[b-1]=cost[a-1]-c
if cost[N-1]!=gendankainokosuto:
    print("inf")
else:
    print(-cost[N-1])

Solution (Python):
import sys

def bellman_ford(n, edges, source):
    """Bellman Ford algorithm

    n: int, the number of nodes.
    edges: list, [edge1, edge2, ... ]
           edge_i = [node, neighbour, weight of the edge]
    source: int, start node.
    """
    
    inf = float('inf')
    dist=[inf for i in range(n)]
    dist[source] = 0

    
    for i in range(n):
        for edge in edges:
            if 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:
                    return -1

    return dist


def main():
    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-1, b-1, -c))

    dist = bellman_ford(N, edges, 0)

    if dist == -1:
        return 'inf'
    else:
        return int(-dist[N-1])


if __name__ == '__main__':
    print(main())

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

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()


edges = []
for _ in range(m):
    ai, bi, ci = li()
    ai -= 1
    bi -= 1
    edges.append((ai, bi, ci))


dist = [[-10**18]*n for _ in range(2*n+3)]
for i in range(2*n+2):
    dist[i][0] = 0

ans = -10**18
chk = -10**18

for i in range(2*n+2):
    for ai, bi, ci in edges:
        dist[i+1][bi] = max(dist[i+1][bi],
                            dist[i][bi],
                            dist[i][ai] + ci)
    if i == n:
        ans = dist[i][n-1]
        
    elif i == 2*n+1:
        chk = dist[i][n-1]
        
print(ans if ans >= chk else "inf")

Solution (Python):
def bellman_ford(vertex_num: int, edges: list, source: int, sink: int) -> list:
    
    distances = [float('inf')] * (vertex_num)
    distances[source] = 0

    
    for _ in range(vertex_num):
        for u, v, c in edges:
            distances[v] = min(distances[v], distances[u] + c)

    
    for u, v, c in edges:
        if distances[u] + c < distances[v]:
            distances[v] = distances[u] + c

            if v == sink:
                return []

    return distances


def score_attack(N: int, M: int, edges: list) -> int:
    distances = bellman_ford(N, [(u-1, v-1, -c) for u, v, c in edges], 0, N-1)

    return -distances[N - 1] if distances else float('inf')


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(M)]
    ans = score_attack(N, M, edges)
    print(ans)

Solution (Python):
inf = float('inf')



def bellmanford(dist,edges,N,end):
    for i in range(N):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                
                
                if i == N-1 and nv == end:
                    return False
    return True

N,M = map(int,input().split())
info = []
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1; b -= 1; c = -c
    info.append((a,b,c))
 
dist = [inf for _ in range(N)]
dist[0] = 0

flag = bellmanford(dist,info,N,N-1)
ans = -dist[N-1] if flag else "inf"
print(ans)

Solution (Python):
inf = float('inf')



def bellmanford(dist,edges,N):
    for i in range(N):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
                
                
                if i == N-1 and nv == N-1:
                    return False
    return True

N,M = map(int,input().split())
info = []
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1; b -= 1; c = -c
    info.append((a,b,c))
 
dist = [inf for _ in range(N)]
dist[0] = 0

flag = bellmanford(dist,info,N)
ans = -dist[N-1] if flag is True else "inf"
print(ans)

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

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


if __name__ == '__main__':
    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())

Solution (Python):
n, m = map(int,input().split())

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

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

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

dist = [INF] * n

dist[0] = 0

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

ans = - dist[n-1]

negative = [False] * n

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

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

Solution (Python):

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

Solution (Python):
N,M=map(int,input().split())
big=10**13
data=[-1*float('inf')]*(N+1)
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
from collections import deque
check=deque()
check.append((1,0,set()))
data[1]=0
while len(check)>0:
    now=check.popleft()
    for b,c in branch[now[0]]:
        if now[1]+c>data[b]:
            if data[b]>big:continue
            if b in now[2]:
                data[b]=float('inf')
                check.append((now[0],float('inf'),now[2]|{now[0],b}))
                check.append((b,float('inf'),now[2]|{now[0],b}))
            else:
                data[b]=now[1]+c
                check.append((b,now[1]+c,now[2]|{now[0],}))
if data[N]>big:print('inf')
else:print(data[N])

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

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

Solution (Python):
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [{} for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        adj[a][b] = c
    points = [-float("inf")] * (N+1)
    q = deque([(1, 0, {})])
    while len(q):
        cur, point, visited = q.popleft()
        if point <= points[cur]:
            continue
        points[cur] = max(points[cur], point)
        nvisited = {v: visited[v] for v in visited}
        nvisited[cur] = point
        for nxt in adj[cur]:
            npoint = point + adj[cur][nxt]
            if nxt in nvisited and nvisited[nxt] < npoint:
                npoint = float("inf")
            q.append((nxt, npoint, nvisited))
    print(points[N])


if __name__ == "__main__":
    main()