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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    u,v,c = map(int,input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    
score = [None]*n
score[0] = 0
prev = score
for i in range(n+3):
    update = False
    for u in range(n):
        if prev[u] is not None:
            for c,v in ns[u]:
                if score[v] is None or score[v]<prev[u]+c:
                    score[v] = prev[u]+c
                    update = True
    if not update:
        print(score[-1])
        break
    prev = score
else:
    reach = [False]*n
    for i in range(n+1):
        for u in range(n):
            if prev[u] is not None:
                for c,v in ns[u]:
                    if score[v] is None or score[v]<prev[u]+c:
                        score[v] = prev[u]+c
                        reach[v] = True
    if reach[-1]:
        print("inf")
    else:
        print(score[-1])

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

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

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

if __name__ == "__main__":
    main()

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

Solution (Python):
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")
        exit()
      dist[b] = dist[a]+c
ans = dist[n]
print(ans)

Solution (Python):
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")
        exit()
      dist[b] = dist[a]+c
ans = dist[n]
print(ans)

Solution (Python):
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford, connected_components
from scipy.sparse.csgraph._shortest_path import NegativeCycleError

input = sys.stdin.buffer.readline


N, M = map(int, input().split())
starts = []
ends = []
costs = []
for _ in range(M):
    a, b, c = map(int, input().split())
    starts.append(a-1)
    ends.append(b-1)
    if c != 0:
        costs.append(-c)
    else:
        costs.append(sys.float_info.epsilon)

look_for_loop = csr_matrix((costs + [0], (starts + [N-1], ends + [0])), shape = (N, N))
_, labels = connected_components(look_for_loop, connection = "strong")
mask = (labels == labels[0])

graph = csr_matrix((costs, (starts, ends)), shape = (N, N)).toarray()
graph = graph[mask, :][:, mask]

try:
    ans = bellman_ford(graph, directed = True, indices = [0])[0][-1]
    ans = int(round(-ans))
except NegativeCycleError:
    ans = "inf"

print(ans)

Solution (Python):
import sys
from _collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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]

def main():
    N, M = map(int, readline().split())
    edges = []
    for _ in range(M):
        u,v,c = map(int, readline().split())
        edges.append([u-1,v-1,-c])

    d = [INF]*N
    d[0] = 0
    for i in range(N-1):
        for j in range(M):
            u, v, c = edges[j]
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
    ans = d[N-1]

    negative_loop = [False]*N
    for i in range(N):
        for j in range(M):
            u, v, c = edges[j]
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                negative_loop[v] = True
            if negative_loop[u]==True:
                negative_loop[v]=True

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




if __name__ == '__main__':
    main()

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

def Bellman_Ford(S,V,E,distance):
    min_distance = [float("inf")]*V 
    min_distance[S-1] = 0 
    count = 1
    while count < 2*V:
        if count == V:
            tmp = min_distance[N-1]
        count += 1
        for s,g,d in distance: 
            if min_distance[s] != float("inf") and min_distance[s] + d < min_distance[g]: 
                min_distance[g] = min_distance[s] + d 
    return min_distance,tmp

min_distance,ansN = Bellman_Ford(1,N,M,line)
ans2N = min_distance[N-1]
if ansN == ans2N:
    print(-ansN)
else:
    print("inf")

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


if __name__ == '__main__':
    main()

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

Solution (Python):
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 = float("inf")
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 ] )

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

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

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

Solution (Python):
N,M = map(int,input().split())
abc = []
for _ in range(M):
    abc.append(list(map(int,input().split())))

cost = [-(10**10)*N]*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)

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

from collections import deque
ls = [deque([]) for _ in range(N)]

for i in range(M):
    a,b,c = 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)

Solution (Python):
n, m = map(int, input().split())
NMAX = 1000; MMAX = 2000

INF = 10**15

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


dist = [INF for _ in range(NMAX)] 
dist[0] = 0
for loop in range(n):
    for i in range(m):
        a, b, c = edge[i]
        if dist[a] == INF:
            continue
        dist[b] = min(dist[b], dist[a]+c)

ans = dist[n-1]




negative = [False for _ in range(NMAX)] 
for loop in range(n):
    for i in range(m):
        a, b, c = edge[i]
        if dist[a] == 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):
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)


if __name__ == "__main__":
	main()

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

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 1000000007


def bellman_ford(edges, num_v, sv):
    
    dist = [INF] * num_v
    dist[sv] = 0
    
    
    for i in range(num_v - 1):
        for edge in edges:
            s, t, d = edge[0], edge[1], edge[2]
            if dist[s] != INF and dist[t] > dist[s] + d:
                dist[t] = dist[s] + d
    
    return dist


def main():
    N, M = map(int, input().split())

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

    negative = [False]*N
    for _ in range(N):
        for edge in edges:
            s, t, d = edge[0], edge[1], edge[2]
            if dist[s] == INF:
                continue
            if dist[t] > dist[s] + d:
                dist[s] = dist[t] + d
                negative[t] = True
            if negative[s] == True:
                negative[t] = True

    if negative[N-1] == True:
        print("inf")
    else:
        print(-dist[N-1])


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    edge=[]
    for i in range(M):
        a,b,c=map(int1,input().split())
        c+=1
        edge.append((a,b,-c))
    d=[INF]*N
    d[0]=0
    f=False
    for i in range(N*2):
        for a,b,c in edge:
            if d[b]>d[a]+c:
                if i<N-1:
                    d[b]=d[a]+c
                else:
                    if d[a]<10**17:
                        d[b]=-INF
                    if b==N-1:
                        f=True
    if f:
        print('inf')
    else:
        print(-d[N-1])

if __name__ == '__main__':
    main()

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

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15

N,M = map(int,input().split())
edge = []
G = [[] for _ in range(N)]
G_inv = [[] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G_inv[b].append(a)
    edge.append((a,b,-c))

can_reach_from_start = [False] * N
can_reach_from_goal = [False] * N
def dfs(i,reach,Gragh):
    for e in Gragh[i]:
        if reach[e]:
            continue
        reach[e] = True
        dfs(e,reach,Gragh)

can_reach_from_start[0] = True
dfs(0,can_reach_from_start,G)
can_reach_from_goal[-1] = True
dfs(N - 1,can_reach_from_goal,G_inv)

X = 0
for i in range(N):
    if can_reach_from_goal[i] and can_reach_from_start[i]:
        X += 1

new_edge = []
for a,b,c in edge:
    if can_reach_from_start[a] and can_reach_from_goal[b]:
        new_edge.append((a,b,c))

def beruman(N,edges,start = 0,negative_loop = False):
    find_negative = False 
    dist = [INF] * N
    dist[start] = 0

    for i in range(X):
        update = False
        for a,b,c in edges:
            if dist[a] != INF and dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                update = True

        if not update:
            break
        if i == X - 1:
            find_negative = True
    
    if negative_loop:
        return dist,find_negative
    else:
        return dist

dist,judge = beruman(N,new_edge,0,True)
if judge:
    print('inf')
else:
    print(-dist[-1])

Solution (Python):
N,M = map(int,input().split())
data = [list(map(int,input().split())) for i in range(M)]

import collections

class BellmanFord():
    def __init__(self,N):
        self.N = N
        self.e = collections.defaultdict(list)
    def add(self,u,v,d,directed = False):
        if directed is False:  
            self.e[u].append([v,d])
            self.e[v].append([u,d])
        else:  
            self.e[u].append((v,d))
    def BellmanFord_search(self,s):  
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        while True:
            update = False
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        d[v] = d[u] + c
                        update = True
            if not update:
                break
        return d
    def BellmanFord_negative_bool(self,s):
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        for i in range(self.N):
            for u in self.e.keys():
                for v,c in self.e[u]:
                    if d[v] > d[u] + c:
                        if i != self.N - 1:
                            d[v] = d[u] + c
                        else:
                            d[v] = -float('inf')
                            for i in range(self.N):
                                for u in self.e.keys():
                                    for v, c in self.e[u]:
                                        if d[v] > d[u] + c:
                                            d[v] = d[u] + c
                            if d[N] == -float('inf'):
                                return True,d
                            else:
                                return False,d
        return False,d

G = BellmanFord(N)

for i in range(M):
    G.add(data[i][0],data[i][1],-data[i][2],directed=True)

bool,d = G.BellmanFord_negative_bool(1)
if bool:
    print('inf')
    exit()

print(-d[N])

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

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

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

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

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

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

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

    return dis

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

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

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

for i in range(n):

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

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

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

    return dis

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

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

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

for i in range(2*n):

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

Solution (Python):
class edge:
    def __init__(self, from_node, to_node, cost):
        self.from_node = from_node
        self.to_node = to_node
        self.cost = cost

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

def bellman_ford(s):
    INIT = 10 ** 30
    d = [INIT] * N
    d[s] = 0
    for _ in range(N):
        update = False
        for e in ed:
            if d[e.from_node] != INIT and d[e.to_node] > d[e.from_node] + e.cost:
                d[e.to_node] = d[e.from_node] + e.cost
                update = True
        if not update:
            return d, True
    return 0, False

d, j = bellman_ford(N-1)
if j:
    print(-d[0])
else:
    print("inf")

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

Solution (Python):
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 = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, -c))

    ans = Bellman_Ford(s=0, g=g)
    print(ans)


if __name__ == '__main__':
    main()