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

    else:
        
        ret = dist[N - 1]
        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

        if ret == dist[N - 1]:
            return -ret
        else:
            return 'inf'

    return -dist[N - 1]


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

Solution (Python):
N, M = map(int, input().split())
edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    edges.append([a, b, -c])
def bellman_ford(edges, N):
    dist = [float('inf') for i in range(N)]
    dist[0] = 0
    for i in range(N-1):
        for edge in edges:
            if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
    negative = [False] * N

    for i in range(N):
        for edge in edges:
            if dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                negative[edge[1] - 1] = True
            if negative[edge[0] - 1] == True:
                negative[edge[1] - 1] =True
    
    return 'inf' if negative[-1] else -dist[-1]

print(bellman_ford(edges, N))

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

Solution (Python):
n,m=map(int,input().split(' '))
piece=[0]*m
for i in range(m):
    piece[i]=tuple(map(int,input().split(' ')))

node=[0]+[float('inf')]*(n-1)

for v in range(n-1):
    for e in range(m):
        a,b,c=piece[e]
        if node[b-1] > node[a-1]-c:
            node[b-1] = node[a-1]-c
ans=node[n-1]
for e in range(m):
    a,b,c=piece[e]
    if node[b-1] > node[a-1] - c:
        node[b-1] = node[a-1] -c

if ans != node[n-1]:
    print('inf')
else:
    print(-ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

inf = 10**18
score = [inf] * (N + 1)
score[1] = 0

for _ in range(N - 1):
    for a, b, c in edge:
        score[b] = min(score[b], score[a] + c)

goal = score[N]
for a, b, c in edge:
    score[b] = min(score[b], score[a] + c)


if goal != score[N]:
    print("inf")
else:
    print(-goal)

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

for _ in range(M):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, -cost))
    E[to].append(fr)

def canGo():
    st = [N - 1]
    visited = [False] * N
    visited[N - 1] = True
    while st:
        for to in E[st.pop()]:
            if visited[to]:
                continue
            visited[to] = True
            st.append(to)
    return visited

V = canGo()

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

for i in range(N + 1):
    for fr, to, cost in edges:
        d = minDist[fr] + cost
        if minDist[to] > d:
            if i == N and V[to]:
                print('inf')
                exit()
            minDist[to] = d

print(-minDist[N - 1])

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

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

d = [float("inf") for _ in range(n)]
d[0] = 0

check = [0 for _ in range(n)]

for i in range(n):
    for now, next, weight in edge:
        if d[next] > d[now] + weight:
            d[next] = d[now] + weight
            if i == n-1:
                check[next] = 1
        if i == n-1:
            if check[now]:
                check[next] = 1

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

Solution (Python):

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

def shortest_path(s, n, es):
    
    
    d = [float("inf")] * n
    
    d[s] = 0
    for _ in range(n):
        update = False
        for p, q, r in es:
            
            if d[p] != float("inf") and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        
        if not update:
            break
    return d

n,w = map(int,input().split()) 
es = [] 

for _ in range(w):
    x,y,z = map(int,input().split())
    es.append([x-1, y-1, -z])
    






d = shortest_path(0, n, es)



c = find_negative_loop(n, es, d)




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

Solution (Python):
N,M=map(int,input().split())
graph=[[] for i in range(N+1)]
for _ in range(M):
    a,b,weight=map(int,input().split())
    graph[a].append((b,-weight))
    
class Node():
    def __init__(self,name):
        self.name=name
        self.par=None
        self.d=float("inf")
        
    def relax(self,other,weight):
        if self.d>other.d+weight:
            self.d=other.d+weight
            self.par=other.name
    def relax_(self,other,weight):
         if self.d>other.d+weight:
            self.d=other.d+weight
            return True
         return False
def bellman_ford(graph,s_node):
    N=len(graph)-1
    d_list=[Node(i) for i in range(N+1)]
    
    d_list[s_node].d=0
    for _ in range(N-1):
        
        for node in range(1,N+1):
            for tuple_ in graph[node]:
                point,distance=tuple_
                d_list[point].relax(d_list[node],distance)
    negative=[False for i in range(N+1)]
    for _ in range(N-1):
        
        for node in range(1,N+1):
            for tuple_ in graph[node]:
                point,distance=tuple_
                if d_list[point].relax_(d_list[node],distance):
                    if negative[point]==False:
                        negative[point]=True
                    else:
                        for que in graph[point]:
                            negative[que[0]]=True
    if negative[N]:
        return False

    return d_list[N].d

K=bellman_ford(graph,1)
if K!=False:
    print(-K)
else:
    print("inf")

Solution (Python):
'''
ベルマンフォード法。
始点を固定した時にすべての頂点に対する最短経路を計算する。
負の辺が使われている場合に使う。
負のループがどこかにあればそれだけで検出する。

O(|E||V|)
'''
class BellmanFord():
    def __init__(self, N):
        '''
        Parameters
        ----------
        N:int
            the number of nodes
        '''
        self.N = N
        self.edges = []
    
    def add(self, u, v, d, directed=False):
        '''
        Parameters
        ----------
        u:int
            from node (not 0-index)
        v:int
            to node (not 0-index)
        d:int
            cost
        directed:bool
            there is direction
        '''
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def calc(self, s):
        '''
        Parameters
        ----------
        s:int
            start index (not 0-index)
        
        Returns
        ----------
        list or bool
            d[i] is shortest distances from node[s] to node[i]
            if there is negative loop, return False
        '''
        dist = [float('inf') for i in range(self.N)]
        dist[s-1] = 0
        
        for i in range(self.N):
            for edge in self.edges:
                frm, to, cost = edge[0] - 1, edge[1] - 1, edge[2]
                
                if dist[frm] != float('inf') and dist[to] > dist[frm] + cost:
                    dist[to] = dist[frm] + cost
                    
                    
                    
                    if i == self.N - 1 and to==self.N-1: return False
        return dist[-1]

'''
ABC061-D
N頂点M辺の重み付き有向グラフがあり、
頂点a_iから頂点b_iを重みc_iで結んでいる。
その辺を移動したときスコアc_iが加算される。
頂点1から始まり、頂点Nに駒があるときゲームを終了できる。
頂点1からNまで移動できることは保証されている。
ゲーム終了時のスコアを最大にするような行動をとった時の最大スコアを出力せよ。
スコアが無限に大きくなる場合はinfを出力せよ。

term:
2<=N<=1000
1<=M<=min(N(N-1),2000)
1<=a_i,b_i<=N
-10**9<=c_i<=10**9

input:
3 3
1 2 4
2 3 3
1 3 5

output:
    7
'''

from collections import defaultdict,deque
import sys, bisect, math, itertools, heapq
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n, m = inpl()
graph=BellmanFord(n)
for _ in range(m):
    a, b, c = inpl()
    graph.add(a, b, -c, directed=True)  
result = graph.calc(1)
if result:
    print(-result)
else:
    print("inf")

'''
負になる閉路に頂点Nが入っていなければその閉路を経由して頂点Nにたどりつけない。
'''

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

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

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

renew=set()
from heapq import *
INF=float('inf')
def dijkstra(s,n):
    d = [INF for i in range(n+1)]
    pq = []
    d[s]=0
    heappush(pq,(0,s))
    while pq:
        dist,u = heappop(pq)
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            if (u,v) in renew:
                d[v]=-INF
            renew.add((u,v))
            heappush(pq,(d[v],v))
    return d             
d=dijkstra(1,n)
print(-d[n])

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

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

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

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

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

def shortest_path(s,n,w,es):
  
  
  dist=[float("inf")]*n
  
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

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

visited=[None]*(N+1)
def check_reachable(u):
  visited[u]=True
  if u==N:
    reachable[u]=True
    return True
  elif reachable[u]!=None:
    return reachable[u]  

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    reachable[u]=False
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)

  
elist2=[]
for a,b,nc in elist:
  if reachable[a] and reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

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

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

def shortest_path(s,n,w,es):
  
  
  dist=[float("inf")]*n
  
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

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

visited=[None]*(N+1)
def check_reachable(u):
  visited[u]=True
  if u==N:
    reachable[u]=True
    return True
  elif reachable[u]!=None:
    return reachable[u]  

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    reachable[u]=False
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)

  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

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

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

def shortest_path(s,n,w,es):
  
  
  dist=[float("inf")]*n
  
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

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

visited=[None]*(N+1)
def check_reachable(u):
  visited[u]=True
  if u==N:
    reachable[u]=True
    return True
  elif reachable[u]!=None:
    return reachable[u]  

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)

  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

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

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

def shortest_path(s,n,w,es):
  
  
  dist=[float("inf")]*n
  
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

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

visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    return False

reachable=[False]*(N+1)
for i in range(1,N+1):
  if not reachable[i]:
    visited=[False]*(N+1)
    check_reachable(i)

  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

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

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

def shortest_path(s,n,w,es):
  
  
  dist=[float("inf")]*n
  
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

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

visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)

  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

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

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

def shortest_path(s,n,w,es):
  
  
  dist=[float("inf")]*n
  
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

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

visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:        
        reachable[u]=True
        cnt+=1
        
  if cnt>0:
    return True
  else:
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)

  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

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

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

def shortest_path(s,n,w,es):
  
  
  dist=[float("inf")]*n
  
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

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

visited=[None]*(N+1)
def check_reachable(u):
  if u==N:
    reachable[u]=True
    return True
  
  visited[u]=True
  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        reachable[u]=True
        cnt+=1
        
  if cnt>0:
    return True
  else:
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)

  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

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

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

def shortest_path(s,n,w,es):
  
  
  dist=[float("inf")]*n
  
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

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

visited=[None]*(N+1)
def check_reachable(s,u):
  if u==N:
    reachable_list[s]=True
    return True
  
  visited[u]=True
  for v in graph[u]:
    if not visited[v]:
      check_reachable(s,v)    
  return False

reachable_list=[False]*(N+1)
for i in range(1,N+1):
  visited=[False]*(N+1)
  check_reachable(i,i)

  
elist2=[]
for a,b,nc in elist:
  if reachable_list[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

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

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

print(shortest_path(1))

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

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

print(shortest_path(1))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

INF = float('inf')

def find_negative_loop(n,es,s):
    
    
    dist = [-INF] * n
    dist[s] = 0

    for i in range(n):
        for a,b,c in es:
            if dist[b] < dist[a]+c:
                dist[b] = dist[a]+c
                
                if i == n-1 and b==n-1: 
                        return INF
    return dist[n-1]

ans = find_negative_loop(n,es,0)

if ans == INF:
    print('inf')
    exit()

print(ans)

Solution (Python):
def BellmanFord(s,N,Edge):
    INF=float("inf")
    dist=[INF]*N
    neg=[False]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=min(dist[t],dist[f]+c)
    for i in range(N):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=dist[f]+c
                neg[t]=True
            if neg[f]:
                neg[t]=True
    return dist,neg

n,m=map(int,input().split())
es=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    es.append((a-1,b-1,-c))
    
res, neg =BellmanFord(0,n,es)
if not neg[-1]:
    print(-res[-1])
else:
    print("inf")

Solution (Python):
class Edge:

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


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


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


if __name__ == '__main__':
    main()

Solution (Python):
import sys


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


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


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

    print(-1 * D[-1])


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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


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


def main():
    pass


if __name__ == "__main__":
    main()


def bellman_ford(edges, N, start, goal):
    dist = [float("inf") for _ in range(N)]
    dist[start] = 0

    
    
    
    
    for i in range(N * 2):
        for fro, to, cost in edges:
            if dist[to] > dist[fro] + cost:
                dist[to] = dist[fro] + cost
                
                if i == N - 1:
                    dist[to] = -float("inf")

    return -dist[goal]


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

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

cost = [float("inf") for _ in range(N)]
start = 0
goal = N - 1
ans = bellman_ford(edges, N, start, goal)
if ans == float("inf"):
    print(ans)
else:
    print(ans)