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 bell(edges, n):
    count = 0
    dist = [float('inf') for i in range(n)]
    dist[0] = 0

 
    for i in range(n):
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2] and edge[0] != float('inf'):
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if (i == n - 1) & (edge[1] == n - 1):
                    print('inf')
                    exit()
                
    return dist
 
 
n,m = map(int,input().split())
edges = []
for _ in range(m):
    a, b, c = (int(x) for x in input().split())
    edges.append([a-1, b-1, -c])
 
res = bell(edges, n)
 
print(-res[n-1])

Solution (Python):
N, M = map(int, input().split())
Edges = []
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    c = -c
    Edges.append([a, b, c])
 
dist = [float('inf')] * N
dist[0] = 0
 
for i in range(N):
    for fr, to, cost in Edges:
        if (dist[fr] != float('inf')) and (dist[to] > dist[fr] + cost):
            dist[to] = dist[fr] + cost
            if (i == N - 1) & (to == N - 1):
                print('inf')
                exit()
 
print(-dist[-1])

Solution (Python):

def bellmanFord(e,n,s):
    inf = 10**18
    d = [inf]*n
    d[s] = 0

    loop = False
    for i in range(n):
        updated = False
        for v in range(n):
            for u,c in e[v]:
                if d[v]!=inf and d[u]>d[v]+c:
                    d[u] = d[v]+c
                    updated = True
                    if i==n-1 and u==n-1:
                        loop = True
        if not updated:
            break
    return d,loop


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

d,loop = bellmanFord(e,n,0)
if loop:
    print("inf")
else:
    print(-d[n-1])

Solution (Python):
N, M = map(int, input().split())
abc = [[int(x) for x in input().split()] for _ in range(M)]
Edges = [None]*M
for i in range(M):
    Edges[i] = (abc[i][0]-1, abc[i][1]-1, -abc[i][2])
def bellman_ford(N, edges, s):
    dist = [float("inf")]*(N)
    dist[s] = 0
    for n in range(N):
        for (u,v,c) in edges:
            if dist[u] != float("inf") and dist[v] >  dist[u] + c:
                dist[v] = dist[u] + c
                if n == N-1 and v == N-1:
                    return "inf"
    return -dist[-1]
print(bellman_ford(N, Edges, 0))

Solution (Python):
n,m = map(int,input().split())
vve = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b,e in vve:
  graph[a].append((b,-e))
score = [10**15 for i in range(n+1)]
score[1] = 0
for j in range(n+1):
  flg = 0
  for i in range(m):
    v1,v2,e = vve[i]
    e = -e
    if score[v1] != 10**15 and score[v2] > score[v1]+e:
      score[v2] = score[v1]+e
      flg = 1
      if j == n-1:
        p = -score[n]
      if j == n:
        q = -score[n]
  if flg == 0:
    break
if flg == 0:
  print(-score[n])
else:
  if p == q:
    print(p)
  else:
    print("inf")

Solution (Python):
def bellman_ford(edges, n, src):
    
    
    inf = float('inf')
    dist = [inf for _ in range(n)]
    dist[src] = 0
    
    pre = {}

    
    for i in range(n-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]
                pre[edge[1]] = edge[0]

    
    def checkpath(pre, n, src):
        if src in pre and pre[n-1] == src and pre[src] == n-1:
            return True
        count = 0
        p = pre[n-1]
        while p != src:
            p = pre[p]
            if p == src and src in pre:
                return True
            count += 1
            if count >= n-1:
                return True
        return False

    is_cycle = checkpath(pre, n, src)
    return (dist, is_cycle)


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

d, is_cycle = bellman_ford(edges, N, 0)
if is_cycle:
    print('inf')
else:
    print(-d[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):
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):
def solve(n, m, ABC):
    distance = [None] * n
    distance[0] = 0

    for _ in range(n - 1):
        for a, b, c in ABC:
            if distance[a - 1] is None:
                continue
            if distance[b - 1] is None or distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c

    for _ in range(n - 1):
        for a, b, c in ABC:
            if distance[a - 1] is None or distance[b - 1] is None:
                continue
            if distance[b - 1] < distance[a - 1] + c:
                distance[b - 1] = distance[a - 1] + c
                if b == n:
                    return 'inf'

    return distance[n - 1]

_n, _m = map(int, input().split())
_ABC = [list(map(int, input().split())) for _ in range(_m)]
print(solve(_n, _m, _ABC))

Solution (Python):
def bellmanford(num, start, goal, edges):
    cost = [float('inf')] * num
    cost[start] = 0
    for _ in range(num):
        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[goal])

def main():
    N, M = LI()
    v = []
    for _ in range(M):
        x, y, z = map(int, input().split())
        v.append((x - 1, y - 1, -z))


    cur, d = bellmanford(N, 0, N - 1, v)
    if cur == -1:
        
        inf_flag = [False] * N
        for _ in range(N):
            for f, t, c in v:
                if d[f] == 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)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    main()

"""
3 3
1 2 4
2 3 3
1 3 5
"""

Solution (Python):

def Bellman_Ford(node_num:int,start:int,goal:int,VWC:list)->list:
    Ans = [float("inf")]*(node_num + 1)
    node = start
    Ans[start] = 0        
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    Pre = list(Ans)
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    if Ans[goal] == Pre[goal]:
        return Ans[goal]
    else:
        return float("inf")
def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in  range(M)]
    newABC = [[a,b,-c] for a,b,c in ABC]
    ans = Bellman_Ford(N,1,N,newABC)
    print(-ans if ans < float("inf") else "inf")
    return


if __name__ == "__main__":
    main()

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

INF = 10**20
V = [INF]*N
V[0] = 0
for _ in range(N):
  for a, b, c in E:
    d = V[a]+c
    if d < V[b]: V[b] = d

R = [False]*N
R[-1] = True
for _ in range(N):
  for a, b, c in E:
    R[a] |= R[b]

for a, b, c in E:
  if V[a]+c<V[b] and R[b]:
    print('inf')
    exit()
    
print(-V[-1])

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    
    N, M = Scanner.map_int()

    class Edge():
        def __init__(self, a, b, c):
            self.from_ = a
            self.to_ = b
            self.cost_ = c
    edges = [Edge] * M
    for i in range(M):
        a, b, c = Scanner.map_int()
        a -= 1
        b -= 1
        c = -c
        edges[i] = Edge(a, b, c)
    dist = [INF] * N
    dist[0] = 0
    for loop in range(N-1):
        for i in range(M):
            e = edges[i]
            if dist[e.from_] == INF:
                continue
            if dist[e.to_] > dist[e.from_] + e.cost_:
                dist[e.to_] = dist[e.from_] + e.cost_
    ans = dist[N-1]
    negatives = [False] * N
    for loop in range(N):
        for i in range(M):
            e = edges[i]
            if dist[e.from_] == INF:
                continue
            if dist[e.to_] > dist[e.from_] + e.cost_:
                dist[e.to_] = dist[e.from_] + e.cost_
                negatives[e.to_] = True
            if negatives[e.from_]:
                negatives[e.to_] = True
    if negatives[N-1]:
        print("inf")
    else:
        print(-ans)


if __name__ == "__main__":
    main()

Solution (Python):



import sys
 
inf = float('inf')
 
n, m = map(int, sys.stdin.readline().split())
abc = []
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    abc.append((a-1, b-1, -c))
 
def main():
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n-1):
        for a, b, c in abc:
            dist[b] = min(dist[b], dist[a] + c)
 
    for _ in range(n):
        for a, b, c in abc:
            if dist[a] + c < dist[b]:
                dist[b] = -inf
 
    return -dist[n-1]
 
if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)




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

EDGES = []

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

INF = 10 ** 18
d = [INF] * (N+1)
d[1] = 0

ans = 0
for k in range(N):
    update = False
    for i in range(M):
        a, b, c = EDGES[i]
        if d[a] != INF and d[b] > d[a] + c:
            d[b] = d[a] + c
            update = True

            if k == N-1 and b == N:
                print('inf')
                exit()

    if not update:
        break

print(-d[N])

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

def main():
    N, M = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    INF = float("inf")
    cost = [-INF] * N
    cost[0] = 0
    for i in range(N-1):
        for a, b, c in ABC:
            cost[b-1] = max(cost[b-1], cost[a-1] + c)
    prev = cost[N-1]
    for a, b, c in ABC:
        cost[b-1] = max(cost[b-1], cost[a-1] + c)    
    print(cost[N-1] if cost[N-1] == prev else "inf")

if __name__ == "__main__":
    main()

Solution (Python):
def shortest_path(s,n,w,es):


    d = [float('inf')] * n
    
    d[s] = 0
    while True:
        for p,q,r in es:
        
            
            if d[p] != float('inf') and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
            ans1=d[-1]
        update = False
        for p,q,r in es:
        
            
            if d[p] != float('inf') and d[q] > d[p] + r:
                d[q] = d[p] + r
            ans2=d[-1]
        return -ans1 if ans1==ans2 else 'inf' 

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])
print(shortest_path(0,n,w,es))

Solution (Python):
N, M = map(int,input().split())
side = [[]for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    side[a-1].append([b-1,c])
node = [-float('inf')]*N
node[0] = 0
for _ in range(N):
    for i in range(N):
        for b,c in side[i]:
            node[b] = max(node[b],node[i]+c)


for _ in range(N):
    for i in range(N):
        for b,c in side[i]:
            if node[b] < node[i]+c:
                node[b] = float('inf')
print(node[-1])

Solution (Python):
N,M=[int(x) for x in input().split()]
A=[]
B=[]
C=[]

for i in range(M):
	a,b,c=[int(x) for x in input().split()]
	A.append(a-1)
	B.append(b-1)
	C.append(-c)
INF=10000000000000
dist=[INF for i in range(N)]

dist[0]=0


for temp in range(N-1):
	for i in range(M):
		if dist[A[i]]!=INF:
			if dist[B[i]]>dist[A[i]]+C[i]:
				dist[B[i]]=dist[A[i]]+C[i]

checker=[0 for i in range(N)]
ans=dist[N-1]

for temp in range(N):
	for i in range(M):
		if dist[A[i]]!=INF:
			if dist[B[i]]>dist[A[i]]+C[i]:
				dist[B[i]]=dist[A[i]]+C[i]
				checker[B[i]]=1
			if checker[A[i]]==1:
				checker[B[i]]=1

if checker[N-1]==1:
	print("inf")
else:
	print(-ans)

Solution (Python):
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
to=[[]for _ in range(n)]
ot=[[]for _ in range(n)]
dic={}
for i in range(m):
    a,b,c=map(int,input().split())
    to[a-1].append([b-1,-c])
    ot[b-1].append([a-1,-c])

vi_to=[0]*n
vi_to[0]=1
from collections import deque
que=deque()
que.append(0)
while que:
    v=que.pop()
    for u,c in to[v]:
        if vi_to[u]:
            continue
        vi_to[u]=1
        que.appendleft(u)

vi_ot=[0]*n
vi_ot[n-1]=1
que=deque()
que.append(n-1)
while que:
    v=que.pop()
    for u,c in ot[v]:
        if vi_ot[u]:
            continue
        vi_ot[u]=1
        que.appendleft(u)

av=[0]*n
for i in range(n):
    if vi_to[i] and vi_ot[i]:
        av[i]=1


dist=[float("inf")]*n
dist[0]=0
for i in range(n):
    for a,toa in enumerate(to):
        for b,c in toa:
            if av[a] and av[b]:
                if dist[b]>dist[a]+c:
                    dist[b]=dist[a]+c
                    if i==n-1:
                        print("inf")
                        exit()

print(-dist[n-1])

Solution (Python):


def mii():
    return map(int, input().split())

from heapq import heappush, heappop

def resolve():
    N, M = mii()
    ab = [[] for i in range(N)]
    for i in range(M):
        a, b, c = mii()
        ab[a-1].append((b-1, c))

    used = [False] * N
    q = [(0, set())]
    while q:
        p1, s1 = q.pop()

        for p2, x in ab[p1]:
            if p2 in s1:
                print("inf")
                return

            s2 = set(s1)
            s2.add(p2)
            q.append((p2, s2))

    q = []
    heappush(q, (0, 0))
    dp = [10**9*N+1] * N
    while q:
        t1, p1 = heappop(q)

        for p2, t2 in ab[p1]:
            t3 = t1 - t2
            if t3 < dp[p2]:
                dp[p2] = t3
                heappush(q, (t3, p2))

    print(-dp[-1])

def resolve():
    N, M = mii()
    ab = [[] for i in range(N)]
    for i in range(M):
        a, b, c = mii()
        ab[a-1].append((b-1, c))


    INF = 10**9*N + 1
    dp = [-INF] * N
    dp[0] = 0
    for i in range(N + 1):
        updated = False
        for p1 in range(N):
            if dp[p1] == -INF: continue

            for p2, t2 in ab[p1]:
                t3 = dp[p1] + t2
                if t3 > dp[p2]:
                    dp[p2] = t3

                    updated = True
        if i == N-1:
            dp0 = dp[-1]
        elif i == N:
            dp1 = dp[-1]
            if dp0 == dp1:
                print(dp1)
            else:
                print("inf")

        if not updated:
            print(dp[-1])
            return



if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 14
    n, m = MI()
    ee = []
    
    for _ in range(m):
        a, b, c = MI()
        a, b = a - 1, b - 1
        ee.append([a, b, -c])
    
    
    
    score = [inf] * n
    score[0] = 0
    for _ in range(n):
        change = False
        for a, b, c in ee:
            if score[a] + c < score[b]:
                score[b] = score[a] + c
                change = True
        if not change:
            print(-score[n - 1])
            exit()
    
    reachable = [False] * n
    for _ in range(n):
        for a, b, c in ee:
            if reachable[a]:reachable[b]=True
            if score[a] + c < score[b]:
                score[b] = score[a] + c
                reachable[b] = True
        if reachable[n - 1]:
            print("inf")
            exit()
    print(-score[n-1])

main()

Solution (Python):
INF = float('inf')
def bellmanford(n, edges, r):  
    d = [INF] * n
    d[r] = 0
    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1 and v == n-1:
                    return 'inf'
    return -d[n-1]


N, M = map(int, input().split())
edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    edges[i] = (a-1, b-1, -c)
ans = bellmanford(N, edges, 0)
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    
    res = [INF] * N
    res[src] = 0
    
    for _ in range(N-1):
        for u, v, cost in edges:
            
            if res[u] == INF:
                continue
            if res[v] > res[u] + cost:
                res[v] = res[u] + cost
    tmp = res[:]
    
    for _ in range(N-1):
        for u, v, cost in edges:
            if res[u] == INF:
                continue
            if res[v] > res[u] + cost:
                
                res[v] = -INF
    for i in range(N):
        if tmp[i] != res[i]:
            res[i] = -INF
    return res

N, M = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, -c))

res = bellman_ford(N, edges, 0)

if res[N-1] != -INF:
    print(-res[N-1])
else:
    print('inf')

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    
    res = [INF] * N
    res[src] = 0
    
    for _ in range(N-1):
        for u, v, cost in edges:
            if res[v] > res[u] + cost:
                res[v] = res[u] + cost
    tmp = res[:]
    
    for _ in range(N-1):
        for u, v, cost in edges:
            if res[v] > res[u] + cost:
                res[v] = res[u] + cost
    for i in range(N):
        if tmp[i] != res[i]:
            res[i] = -INF
    return res

N, M = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, -c))

res = bellman_ford(N, edges, 0)

if res[N-1] != -INF:
    print(-res[N-1])
else:
    print('inf')

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    
    res = [INF] * N
    res[src] = 0
    
    for _ in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    ans = res[N-1]
    
    for _ in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    if ans != res[N-1]:
        
        return []
    
    return res

N, M = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    edges.append((a, b, -c))

res = bellman_ford(N, edges, 0)

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

Solution (Python):
def bellman_ford(edges, start, n):
    inf = float('INF')
    costs = [inf] * n
    
    costs[start]= 0

    for e in edges:
        u,v,c = e
        if costs[v] > costs[u] + c:
            costs[v] = costs[u] + c
            

    ans = costs[-1]
    for u,v,c in edges:
        if costs[v] > costs[u] + c:
            costs[v] = costs[u] + c

    return -ans if costs[-1] == ans else 'inf'

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

Solution (Python):

def bellman_ford(edges, start, n):
    inf = float('INF')
    costs = [inf] * n
    predecessors = [-1] * n
    costs[start]= 0

    for _ in range(n-1):
        for e in edges:
            u,v,c = e
            if costs[v] > costs[u] + c:
                costs[v] = costs[u] + c
                predecessors[v] = u

    ans = costs[-1]
    for u,v,c in edges:
        if costs[v] > costs[u] + c:
            costs[v] = costs[u] + c

    return -ans if costs[-1] == ans else 'inf'

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

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

class edge:
    def __init__(self, source, destination, weight):
        self.from_ = source
        self.to_ = destination
        self.weight = weight

    def values(self):
        return self.from_, self.to_, self.weight

def bellman_ford(edges, start, n):
    costs = [inf] * n
    predecessors = [-1] * n
    costs[start]= 0

    for _ in range(n-1):
        for u in range(n):
            for v,w in edges[u].items():
                if costs[v] > costs[u] + w:
                    costs[v] = costs[u] + w
                    predecessors[v] = u

    v = n-1
    while v > 0:
        u = predecessors[v]
        if costs[v] > costs[u] + edges[u][v]:
            return 'inf'
        v = u

    return -costs[n-1]

n,m = map(int, input().split())
edges = [{} for _ in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    edges[a-1][b-1] = -c
print(bellman_ford(edges, 0, n))

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse.csgraph import connected_components

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

row, col, val = zip(*ABC)

val = [-(x) for x in val]
graph = csr_matrix((val,(row,col)),(N+1,N+1))


find_component_graph = csr_matrix(([1]*(M+1),(row+(N,),col+(1,))),(N+1,N+1))

n, labels = connected_components(find_component_graph,connection = 'strong')
idx = (labels == labels[1]) 
graph = graph[idx,:][:,idx]

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

print(answer)

Solution (Python):
def bellman_ford(edges, n, src):
    
    
    inf = float('inf')
    dist = [inf for _ in range(n)]
    dist[src] = 0
    
    pre = {}

    
    for i in range(n-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]
                pre[edge[1]] = edge[0]

    
    def checkpath(pre, n, src):
        if src in pre and pre[n-1] == src and pre[src] == n-1:
            return True
        count = 0
        p = pre[n-1]
        while p != src:
            p = pre[p]
            if p == src and src in pre:
                return True
            count += 1
            if count >= n-1:
                return True
        return False

    is_cycle = checkpath(pre, n, src)
    return (dist, is_cycle)


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

d, is_cycle = bellman_ford(edges, N, 0)
if is_cycle:
    print('inf')
else:
    print(-d[N-1])

Solution (Python):
"""

問題:
N 頂点 M 辺の重み付き有向グラフがあります。
i(1≦i≦M) 番目の辺は 頂点 ai から 頂点 bi を重み ciで結びます。
このグラフと駒を利用して、次の1人ゲームを行います。
最初、駒を頂点 1に置いて、プレイヤーのスコアを 0とします。
プレイヤーは、次の条件で駒を繰り返し移動させることができます。
- 頂点 aiに駒があるとき、i 番目の辺を利用して頂点 bi に移動する。移動後にプレイヤーのスコアが ci加算される。
頂点 Nに駒があるときのみ、ゲームを終了できます。
なお、与えられる有向グラフの上で頂点 1 から頂点 Nに移動できることは保障されています。
プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、ゲーム終了時のスコアはいくつになるでしょうか?
ゲーム終了時のスコアをいくらでも大きくできる場合は inf と出力してください。

制約:
- 2≦N≦1000
- 1≦M≦min(N(N−1),2000)
- 1≦ai,bi≦N(1≦i≦M)
- ai≠bi(1≦i≦M)
- ai≠ajまたは bi≠bj(1≦i<j≦M)
- −10 ** 9≦ci≦10 ** 9(1≦i≦M)
- ciは整数である。
- 与えられるグラフには、頂点 1から頂点 N への経路が存在する。

検討:
- 閉路が存在する場合、スコアをいくらでも大きくできる可能性がある
- 閉路を1周することで得られるスコア合計の符合によってinfにできるかどうかが判定可能
  - 符合が正: inf
  - 符合が0以下: 最短でNに到達したときのスコアが解
- 閉路が複数ある場合はどうするか
  - 1周したときに得られるスコア合計の符合が正かどうかで判断

必要な処理:
- 最短経路探索: ダイクストラ法? -> ベルマンフォード法（コストに正負があるため）
- 閉路を見つけ出す
- 閉路を1周したときのスコア合計

計算時間:
- ベルマンフォード法の時間計算量はO(NM)
- 解説通りにpythonで実装したらTLE判定...(約2100ms)
- 制約通りでいけば、NM = 1000 * 2000 = 2 * 10 ** 6
- 20msの化け物がいる...
"""

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

inf = 10 ** 18
dist = [inf for _ in range(n)]
dist[0] = 0

for i in range(n-1):
    for a, b, c in edges:
        dist[b] = min(dist[b], dist[a] + c)

for i in range(n):
    for a, b, c in edges:
        if dist[a] + c < dist[b]:
            dist[b] = -inf

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