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())
edge = [tuple(map(int, input().split())) for _ in range(m)]

inf = 10 ** 18
dis = [inf] * n
dis[0] = 0

for z in range(2*n+1):
    update = False
    for a, b, c in edge:
        a -= 1
        b -= 1
        if dis[a] != inf and dis[b] > dis[a] - c:
            dis[b] = dis[a] - c
            update = True
            if b == n - 1 and z >= n - 1:
                print('inf')
                exit()
print(-dis[n-1])

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

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

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

dist = bellman_ford(0)
if dist == -1:
  print('inf')
else:
  print(-1*dist[n-1])

Solution (Python):
n,m = map(int, input().split())
link = []
for i in range(m):
    tmp = list(map(int,input().split()))
    link.append([tmp[0]-1,tmp[1]-1,-tmp[2]])

def bell(edges, start,num_v):
    cost = [float('inf')] * num_v
    cost[start] = 0
    for _ in range(num_v):
        updated = False
        for a, b, c in edges:
            if cost[b] > cost[a] + c:
                cost[b] = cost[a] + c
                updated = True
        if not updated: break
    else:
        return -1,cost
    return 1,cost

ans1,d = bell(link,0,n)

if ans1 == -1:
    inf_flag = [False]*n
    for i in range(n):
        for f, t, c in link:
            if d[f] == float("inf"): continue
            if inf_flag[f] == True:
                inf_flag[t] = True
            if d[t] > d[f] + c:
                d[t] = d[f] + c
                inf_flag[t] = True
    print("inf" if inf_flag[n-1] else -d[n-1])
else:
    print(-d[-1])

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    
    def BellmanFord(edges,V,source):
        INF = float("inf")
        dist = [INF for _ in range(N)]
        dist[source] = 0
        
        for i in range(V):
            for now,fol,d in edges:
                if dist[now] != INF and dist[fol] > dist[now]+d:
                    dist[fol] = dist[now]+d
                    if i == V-1 and fol == N-1:
                        return "inf"
        return -1*dist[-1]
        
    edge = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        edge.append((a-1,b-1,-c))
    
    print(BellmanFord(edge,N,0))

if __name__ == "__main__":
    main()

Solution (Python):
n,m = map(int,input().split())
g = sorted([list(map(int,input().split())) for _ in range(m)])
def BellmanFord(edges,num_v,source):
  
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  
  
  for i in range(num_v):
    for edge in edges:
      if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] - edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] - edge[2]
        if i==num_v-1 and edge[0] == num_v-1: 
          return -1
  return dist
if BellmanFord(g,n,1) == -1:
  print("inf")
else:
  print(-BellmanFord(g,n,1)[-1])

Solution (Python):
n,m = map(int,input().split())
g = sorted([list(map(int,input().split())) for _ in range(m)])
def BellmanFord(edges,num_v,source):
  
  inf=float("inf")
  dist=[inf for i in range(num_v)]
  dist[source-1]=0
  
  
  for i in range(num_v):
    for edge in edges:
      if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] - edge[2]:
        dist[edge[1]-1] = dist[edge[0]-1] - edge[2]
        if i==num_v-1 and edge[0] == num_v-1: return -1
  
  return dist
if BellmanFord(g,n,1) == -1:
  print("inf")
else:
  print(-BellmanFord(g,n,1)[-1])

Solution (Python):
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    
    def BellmanFord(adj, start):
        N = len(adj) - 1
        inf = 10**13
        dist = [inf] * (N + 1)
        dist[start] = 0
        neg_loop_flg = 0
        for i in range(N):
            updated = 0
            for fr in range(1, N + 1):
                if dist[fr] == inf:
                    continue
                for to, cost in adj[fr]:
                    if dist[fr] + cost < dist[to]:
                        dist[to] = dist[fr] + cost
                        updated = 1
            if not updated:
                break
            if i == N - 1:
                if updated:
                    neg_loop_flg = 1

        return dist, neg_loop_flg

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

    adj_new = [[] for _ in range(N+1)]
    que = deque()
    que.append(N)
    seen = [0] * (N+1)
    seen[N] = 1
    while que:
        v = que.pop()
        for u, cost in adj[v]:
            if not seen[u]:
                seen[u] = 1
                que.append(u)
            adj_new[u].append((v, cost))

    dist, flg = BellmanFord(adj_new, 1)
    if flg:
        print('inf')
    else:
        print(-dist[N])


if __name__ == '__main__':
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M = LI()
    d = [inf for _ in range(N)]
    d[0] = 0
    edges = []
    for _ in range(M):
        a, b, c = LI_()
        c += 1
        edges.append((a, b, -c))
    for _ in range(N-1):
        for edge in edges:
            fr, to, cost = edge
            if d[to] > d[fr] + cost:
                d[to] = d[fr] + cost
    neg = [False for _ in range(N)]
    for _ in range(N):
        for edge in edges:
            fr, to, cost = edge
            if neg[fr] == True:
                neg[to] = True
            if d[to] > d[fr] + cost:
                neg[to] = True
    if neg[N-1]:
        print('inf')
    else:
        print(-d[N-1])

main()

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

def bf():
    d = [ainf] * n
    d[0] = 0
    i = 0 
    sa = 0
    ta = 0
    
    for i in range(n+1):
        for p,q,r in es:
            if d[p] != ainf and d[q] < d[p] + r:
                d[q] = d[p] + r
                if i == n-1:
                    sa = d[n-1]
                if i == n:
                    ta = d[n-1]
                
    return sa,ta,d[n-1]

for _ in range(m):
    x , y , z = map(int,input().split())
    es.append([x-1,y-1,z])
    
s,t,u = bf()

if s == t:
    print(u)
else:
    print("inf")

Solution (Python):
def Bellman_Ford(G, start, goal):
    V = len(G)
    INF = float('inf')
    negative = [False] * V
    dist = [INF] * V
    dist[start] = 0
    for i in range(V-1):
        UnUpdate = True
        for v, e in enumerate(G):
            for t, cost in e:
                if dist[v] != INF and dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    UnUpdate = False
        if UnUpdate:
            break

    if not UnUpdate:
        for i in range(V):
            UnUpdate = True
            for v, e in enumerate(G):
                for t, cost in e:
                    if dist[v] != INF and dist[v] + cost < dist[t]:
                        dist[t] = dist[v] + cost
                        negative[t] = True
                        for tt, cct in G[t]:
                            negative[tt] = True
                        UnUpdate = False

            if UnUpdate or negative[goal]:
                break
    if negative[goal]:
        return "inf"
    else:
        return 0-dist[goal]


V, E = map(int, input().split())
G = [[] for i in range(V)]
for i in range(E):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, 0-c))
ans = Bellman_Ford(G,0,V-1)
print(ans)

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


def bellman_ford(s, g):
	
	
	dist = [float("inf")] * n
	dist[s] = 0
	for i in range(2 * n):
		for a, b, c in abc:
			a -= 1
			b -= 1
			c = -c

			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					dist[b] = -float("inf")

	if dist[g] == -float("inf"):
		ret = "inf"

	else:
		ret = -dist[g]

	return ret


ans = bellman_ford(0, n - 1)
print(ans)

Solution (Python):
INF = float('inf')
def bellman_ford(n, edges, s):
  min_dist = [INF] * n

  min_dist[s] = 0

  for i in range(n):
    for (start, end, cost) in edges:
      if min_dist[start] != INF and min_dist[start] + cost < min_dist[end]:
        min_dist[end] = min_dist[start] + cost
        if i == n-1 and end == n-1:
          return -INF
  
  return min_dist

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

edges = []

for i in range(M):
  edge = list(map(int, input().split()))
  edge[0] -= 1
  edge[1] -= 1
  edge[2] = -edge[2]
  edges.append(edge)
min_dist = bellman_ford(N, edges, 0)

if min_dist == -INF:
  print('inf')
else:
  print(-min_dist[-1])

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


def Bellmanford(node, edges, source):
    d = [INF] * node  
    d[source] = 0

    for i in range(node):
        for start, goal, cost in edges:
            
            
            
            if d[start] != INF and d[start] + cost < d[goal]:
                d[goal] = d[start] + cost
                if i == node-1 and goal == node-1:
                    return 'inf'
    return -d[node-1]


N, M = map(int, input().split())
abc = [map(int, input().split()) for _ in range(M)]
Edges = [None] * M

for i in range(M):
    ai, bi, ci = abc[i]
    Edges[i] = (ai-1, bi-1, -ci)


ans = Bellmanford(N, Edges, 0)
print(ans)

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

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

E = [[] for _ in range(n+1)]
for i in range(m):
    ai,bi,ci = map(int, input().split( ))
    ai-=1;bi-=1
    E[ai].append((bi,-ci))





INF = 10**18
dist = [INF] * n
dist[0] = 0
update = 1
for _ in range(n):
    update = 0
    for v, e in enumerate(E):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
    if not update:
        break

ans = dist[n-1]


for _ in range(n):
    update = 0
    for v, e in enumerate(E):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
if ans > dist[n-1]:
    print("inf")
else:
    print(-ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
inf = 10 ** 18

N, M = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]

negative = [False] * (N + 1)
cost = [inf] * (N + 1)
cost[1] = 0

for loop in range(N):
    update = False
    for a, b, c in ABC:
        if cost[b] > cost[a] - c:
            cost[b] = cost[a] - c
            if loop == N - 1:
                negative[b] = True

ans = -cost[N]
if negative[N]:
    ans = "inf"
print(ans)

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    inf = float("inf")
    sc = [-inf] * N
    sc[0] = 0
    ans = 0
    for i in range(2 * N):
        for ai, bi, ci in zip(a, b, c):
            ai -= 1
            bi -= 1
            sc[bi] = max(sc[bi], sc[ai] + ci)
        if i == N - 1:
            ans = sc[N - 1]
    if ans < sc[N - 1]:
        print("inf")
        return
    print(sc[N - 1])


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):
INF = float('inf')

def bellman_ford(n, edges, s, e):
    
    
    min_dist = [INF] * n

    
    min_dist[s] = 0

    for i in range(n):
        for (start, end, cost) in edges:
            if min_dist[start] != INF and min_dist[start] + cost < min_dist[end]:
                min_dist[end] = min_dist[start] + cost
                
                if i == n - 1 and end == n - 1:
                    return INF 
    return min_dist

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

graph = []

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

dist = bellman_ford(n, graph, 0, n - 1)
if dist == INF:
    print("inf")
else:
    print(-dist[n - 1])

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

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


def bellman_ford(s, g):
	dist = [float("inf")] * n
	dist[s] = 0
	negative = [False] * n
	for i in range(2 * n):
		for a, b, c in abc:
			a -= 1
			b -= 1
			c = -c

			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					negative[b] = True

	if negative[g]:
		ret = "inf"

	else:
		ret = -dist[g]

	return ret


ans = bellman_ford(0, n - 1)
print(ans)

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

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 (-1)*d[n-1]

N,M=map(int, sys.stdin.readline().split())
Edges=[0]*M

for i in range(M):
  a,b,c=map(int, sys.stdin.readline().split())
  Edges[i]=(a-1,b-1,-c)
    
ans=Bellmanford(N,Edges,0)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

    

def main():
    mod=10**9+7
    N,M=MI()
    edges=[None]*M
    
    for i in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        c*=-1
        edges[i]=(a,b,c)
        
    
    
    def BellmanFord(N, M, edges):
        inf=10**20
        d = [inf] * N
        d[0] = 0

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

        
        for (u, v, c) in edges:
            if d[u] + c < d[v]:
                if v == N-1:
                    return None
                
                d[v] = d[u] + c
        return d[N-1]
    
        
    ans = BellmanFord(N, M, edges)
    if ans is None:
        print('inf')
    else:
        print(-ans)

main()

Solution (Python):
def bellmanFord(edges):
    dist = [float('inf')] * N
    dist[0] = 0
    for _ in range(N-1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    res = -dist[-1]
    neg = [False] * N
    for _ in range(N):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                neg[v] = True
            if neg[u]:
                neg[v] = True
    if neg[-1]:
        res = 'inf'
    return res

N, M = map(int, input().split())
A = [tuple()] * M
for i in range(M):
    a, b, c = map(int, input().split())
    A[i] = (a-1, b-1, -c)
ans = bellmanFord(A)
print(ans)

Solution (Python):
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7




from math import isinf


class Edge(object):

    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost


class BellmanFord(object):

    def __init__(self, v_len, edges, start):
        """
        隣接行列を使っていないので、有向グラフにのみ適用可能。
        ベルマンフォード法によって最短経路を求める。
        ダイクストラと違って負の数も扱えるが、O(|V||E|) なのでダイクストラより遅い。

        :param v_len: グラフのノード数 通常は|V|、1-indexedなグラフなら |V| + 1
        :param edges: 辺のリスト
        :param start: 始点 単一視点最短経路問題として解くので必要
        """
        self._dist = [float('inf') for _ in range(v_len)]  
        self._prev = [float('inf') for _ in range(v_len)]  

        self._solve(edges, start)

    def _solve(self, edges, start):
        self._dist[start] = 0

        cnt = 0
        while True:  
            cnt += 1
            updated = False
            for e in edges:
                if self._dist[e.src] + e.cost < self._dist[e.dst]:
                    self._dist[e.dst] = self._dist[e.src] + e.cost
                    self._prev[e.dst] = e.src
                    if cnt >= len(self._dist):
                        self._dist[e.dst] = float('-inf')
                    updated = True
            if not updated:
                break

    def distance(self, goal):
        """
        負の閉路を含む場合は -inf を返す。
        """
        return self._dist[goal]

    def path(self, goal):
        """
        負の閉路を含む場合は計算が終わらない。
        """
        path = list()
        path.append(goal)
        cursor = goal

        while not isinf(self._prev[cursor]):
            path.append(self._prev[cursor])
            cursor = self._prev[cursor]

        return list(reversed(path))


N, M = MI()
edges = list()
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append(Edge(a, b, -1 * c))
bf = BellmanFord(N + 1, edges, 1)
print(-1 * bf.distance(N))

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

for n in range(N):
    updated = False
    for (i, j, c) in edges:
        
        if score[j-1] < score[i-1] + c:
            score[j-1] = score[i-1] + c
            if j == N-1:
                updated = True
        
    if not updated:
        break

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

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

minimumScore = [float('inf') for _ in range(N)]
minimumScore[0] = 0
for _ in range(N-1):
    flag = False
    for a, b, c in paths:
        c = -c
        if minimumScore[a-1] == -float('inf'):
            continue
        if minimumScore[a-1] + c < minimumScore[b-1]:
            minimumScore[b-1] = minimumScore[a-1] + c
            flag = True
    if not flag:
        break


negative = [False for i in range(N)]
for _ in range(N):
    for a, b, c in paths:
        c = -c
        if negative[a-1]:
            negative[b-1] = True
        if minimumScore[a-1] == -float('inf'):
            continue
        if minimumScore[a-1] + c < minimumScore[b-1]:
            negative[b-1] = True
            flag = True
if negative[-1]:
    print('inf')
else:
    print(-minimumScore[N-1])

Solution (Python):




INF = 1 << 50

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


Sides = []
for i in range (M):
    Side = list(map(int,input().split()))
    Sides.append(Side)

    Sides[i][2] = Sides[i][2] * (-1)


Vertexes = [INF]*(N+1)
Vertexes[1] = 0


negative = [False] * (N+1)


for count in range(N):
    for i in range(M):
        from_v = Sides[i][0]
        to_v = Sides[i][1]
        cost = Sides[i][2]
        if (Vertexes[to_v] > Vertexes[from_v]+cost):

            if(count==N-1):
                negative[to_v] = True
            else:
                Vertexes[to_v] = Vertexes[from_v]+cost


for count in range(N-1):
    flag = 0
    for i in range(M):
        from_v = Sides[i][0]
        to_v = Sides[i][1]
        if negative[from_v] and negative[to_v] is False:
            negative[to_v] = True
            flag = 1
    if flag ==0:
        break

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

Solution (Python):




INF = 1 << 50

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


Sides = []
for i in range (M):
    Side = list(map(int,input().split()))
    Sides.append(Side)

    Sides[i][2] = Sides[i][2] * (-1)


Vertexes = [INF]*(N+1)
Vertexes[1] = 0


negative = [False] * (N+1)


for count in range(N):
    for i in range(M):
        from_v = Sides[i][0]
        to_v = Sides[i][1]
        cost = Sides[i][2]
        if (Vertexes[to_v] > Vertexes[from_v]+cost):
            if(count==N-1):
                negative[to_v] = True
            else:
                Vertexes[to_v] = Vertexes[from_v]+cost


for count in range(N-1):
    flag = 0
    for i in range(M):
        from_v = Sides[i][0]
        to_v = Sides[i][1]
        if negative[from_v] :
            negative[to_v] = True
            flag = 1
    
     

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

Solution (Python):
from collections import defaultdict
N, M, *L = map(int, open(0).read().split())
dic = defaultdict(list)
rdic = defaultdict(list)
nin = [0]*N
Els = []
for a,b,c in zip(*[iter(L)]*3):
  dic[a-1] += [b-1]
  rdic[b-1] += [a-1]
  nin[b-1] += 1
  Els += [(a-1,b-1,c)]

To = [False]*N
From = [False]*N
q = [0]
To[0] = True
while q:
  p = q.pop()
  for e in dic[p]:
    if To[e]==False:
      To[e] = True
      q += [e]
q = [N-1]
From[N-1] = True
while q:
  p = q.pop()
  for e in rdic[p]:
    if From[e]==False:
      From[e] = True
      q += [e]

ok = [False]*N
for i  in range(N):
  ok[i] = To[i]&From[i]

cnt = 0
dist = [-float('inf')]*N
dist[0] = 0
cnt = 0
flag = False
while True:
  update = True
  for a,b,c in Els:
    if not(ok[a] and ok[b]):
      continue
    if dist[a]!=-float('inf') and dist[b]<dist[a]+c:
      dist[b] = dist[a]+c
      update = False
  if update:
    break
  cnt += 1
  if cnt>N:
    flag = True
    break

if flag:
  print('inf')
else:
  print(dist[N-1])

Solution (Python):
from collections import defaultdict
N, M, *L = map(int, open(0).read().split())
dic = defaultdict(list)
rdic = defaultdict(list)
nin = [0]*N
Els = []
for a,b,c in zip(*[iter(L)]*3):
  dic[a-1] += [b-1]
  rdic[b-1] += [a-1]
  nin[b-1] += 1
  Els += [(a-1,b-1,-c)]

To = [False]*N
From = [False]*N
q = [0]
To[0] = True
while q:
  p = q.pop()
  for e in dic[p]:
    if To[e]==False:
      To[e] = True
      q += [e]
q = [N-1]
From[N-1] = True
while q:
  p = q.pop()
  for e in rdic[p]:
    if From[e]==False:
      From[e] = True
      q += [e]

ok = [False]*N
for i  in range(N):
  ok[i] = To[i]&From[i]

cnt = 0
dist = [float('inf')]*N
dist[0] = 0
cnt = 0
flag = False
while True:
  update = True
  for a,b,c in Els:
    if not(ok[a] and ok[b]):
      continue
    if dist[a]!=float('inf') and dist[b]>dist[a]+c:
      dist[b] = dist[a]+c
      update = False
  if update:
    break
  cnt += 1
  if cnt>N:
    flag = True
    break

if flag:
  print('inf')
else:
  print(-dist[N-1])

Solution (Python):
from collections import defaultdict
N, M, *L = map(int, open(0).read().split())
dic = defaultdict(list)
rdic = defaultdict(list)
nin = [0]*N
Els = []
for a,b,c in zip(*[iter(L)]*3):
  dic[a-1] += [b-1]
  rdic[b-1] += [a-1]
  nin[b-1] += 1
  Els += [(a-1,b-1,-c)]

To = [False]*N
From = [False]*N
q = [0]
To[0] = True
while q:
  p = q.pop()
  for e in dic[p]:
    if To[e]==False:
      To[e] = True
      q += [e]
q = [N-1]
From[N-1] = True
while q:
  p = q.pop()
  for e in rdic[p]:
    if From[e]==False:
      From[e] = True
      q += [e]

ok = [False]*N
for i  in range(N):
  ok[i] = To[i]&From[i]

cnt = 0
dist = [float('inf')]*N
dist[0] = 0
cnt = 0
flag = False
while True:
  update = True
  for a,b,c in Els:
    if not(ok[a] and ok[b]):
      continue
    if dist[a]!=float('inf') and dist[b]>dist[a]+c:
      dist[b] = dist[a]+c
      update = False
  if update:
    break
  cnt += 1
  if cnt>2*N:
    flag = True
    break

if flag:
  print('inf')
elif dist[N-1]==float('inf'):
  print('inf')
else:
  print(-dist[N-1])

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

Solution (Python):
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

N,M=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(M)]

idle_max=10**18+1

dist=[idle_max for i in range(N+1)]
dist[1]=0


for loop in range(N-1):
    for a,b,c in ABC:
        c=-c
        if dist[a] != idle_max:
            dist[b]=min(dist[a] + c,dist[b])

value=dist[N]
for loop in range(N):
    for a,b,c in ABC:
        c=-c
        if dist[a] != idle_max:
            dist[b]=min(dist[a] + c,dist[b])
if value!=dist[N]:
    print("inf")
else:
    print(-value)

Solution (Python):
INF = 10 ** 18
N, M = map(int, input().split())
abc = []
d = [INF] * N
d[0] = 0
loop = [False] * N

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

for j in range(N):
    for i in range(M):
        if d[abc[i][1]] > d[abc[i][0]] + abc[i][2]:
            d[abc[i][1]] = d[abc[i][0]] + abc[i][2]
ans = -1 * d[-1]

for i in range(N):
    for j in range(M):
        if d[abc[j][1]] > d[abc[j][0]] + abc[j][2]:
            d[abc[j][1]] = d[abc[j][0]] + abc[j][2]
            loop[abc[j][1]] = True

        if loop[abc[j][0]] == True:
            loop[abc[j][1]] = True

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

Solution (Python):
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15
def search(graph, n, m):
    d = deque()
    for edge in graph[0]:
        d.append(edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    loop = [0 for i in range(n)]
    while(d):
        
        point, cur, nxt = d.popleft()
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                d.append(edge)

            cnt += 1
            if cnt > n:
                loop[nxt] = 1

        if cnt >= n * 2:
            break
    
    if loop[n-1]:
        return "inf"

    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    
    ans = search(graph, n, m)

    print(ans)


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""