Problem:
 Score : 400 points    Problem Statement There is a directed graph with N vertices and M edges.
The i -th edge (1≤i≤M) points from vertex a_i to vertex b_i , and has a weight c_i .
We will play the following single-player game using this graph and a piece.  Initially, the piece is placed at vertex 1 , and the score of the player is set to 0 .
The player can move the piece as follows:   When the piece is placed at vertex a_i , move the piece along the i -th edge to vertex b_i . After this move, the score of the player is increased by c_i .   The player can end the game only when the piece is placed at vertex N .
The given graph guarantees that it is possible to traverse from vertex 1 to vertex N .  When the player acts optimally to maximize the score at the end of the game, what will the score be?
If it is possible to increase the score indefinitely, print inf .      Constraints  2≤N≤1000   1≤M≤min(N(N-1),2000)   1≤a_i,b_i≤N (1≤i≤M)   a_i≠b_i (1≤i≤M)   a_i≠a_j or b_i≠b_j (1≤i<j≤M)   -10^9≤c_i≤10^9 (1≤i≤M)  c_i is an integer.  In the given graph, there exists a path from vertex 1 to vertex N .         Input Input is given from Standard Input in the following format:  N  M  a_1  b_1  c_1  a_2  b_2  c_2  :  a_M  b_M  c_M       Output Print the maximum possible score at the end of the game, if it is finite. If it is possible to increase the score indefinitely, print inf .        Sample Input 1 3 3
1 2 4
2 3 3
1 3 5      Sample Output 1 7  There are two ways to move the piece to vertex N=3 :   vertex 1 → vertex 2 → vertex 3 : score 4+3=7  vertex 1 → vertex 3 : score 5   Thus, the maximum possible score at the end of the game is 7 .       Sample Input 2 2 2
1 2 1
2 1 1      Sample Output 2 inf  It is possible to increase the score indefinitely by alternating between vertex 1 and 2 .       Sample Input 3 6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000      Sample Output 3 -5000000000

Solution (Python):

import sys
input = sys.stdin.readline

def bellman_ford(N: int, M: int, E: "Array[Array[int]]") -> int or None:
    INF = float("inf")
    dist = [INF] * (N + 1)
    dist[1] = 0

    
    for i in range(N):
        for v, u, w in E:  
            if v != INF and dist[v] - w < dist[u]:
                dist[u] = dist[v] - w
                if i == N - 1 and u == N:  
                    return None
    return dist[-1]


def main():
    
    N, M = tuple(map(int, input().split()))  
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    ans = bellman_ford(N, M, E)
    flg = ans is not None
    print(-ans if flg else "inf")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt


args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


def main():
    N, M = input(int, int)
    ABC = input([[int, 3], M])

    
    g = nlist([N + 1], [])
    for a, b, c in ABC:
        g[b] += [(a, c)]

    que, rch = [N], {N}
    while que:
        cur = que.pop()
        for nxt, _ in g[cur]:
            if nxt in rch: continue
            rch |= {nxt}
            que.append(nxt)
    edges = [(a, b, c) for a, b, c in ABC if a in rch and b in rch]

    
    g = nlist([N + 1], INF)
    g[1] = 0
    for _ in range(N):
        f = True
        for a, b, c in edges:
            c = -c
            if g[a] + c < g[b]:
                g[b] = g[a] + c
                f = False
        if f:
            break
    else:
        
        print("inf")
        return
    print(-g[N])
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt


args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


def main():
    N, M = input(int, int)
    ABC = input([[int, 3], M])

    
    g = nlist([N + 1], [])
    for a, b, c in ABC:
        g[b] += [(a, c)]

    que, arl, rch = [N], [False] * (N + 1), {N}
    while que:
        cur = que.pop()
        if arl[cur]: continue
        arl[cur] = True
        for nxt, _ in g[cur]:
            if arl[nxt]: continue
            rch |= {nxt}
            que.append(nxt)
    edges = [(a, b, c) for a, b, c in ABC if a in rch and b in rch]

    
    g = nlist([N + 1], INF)
    g[1] = 0
    for _ in range(N):
        f = True
        for a, b, c in edges:
            c = -c
            if g[a] + c < g[b]:
                g[b] = g[a] + c
                f = False
        if f:
            break
    else:
        
        print("inf")
        return
    print(-g[N])
    return

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Solution (Python):
def main():
    INF = float('inf')
    N, M = map(int, input().split())
    dist = [0] + [INF] * (N-1)
    abc = []
    
    for i in range(M):
        a, b, c = map(int, input().split())
        abc.append((a-1, b-1, -c))
            
    for a, b, c in abc:
        dist[b] = min(dist[b], dist[a]+c)
        
    ans = dist[-1]
    
    for a, b, c in abc:
        dist[b] = min(dist[b], dist[a]+c)
            
    if ans != dist[-1]:
        print('inf')
    else:
        print(-ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    INF = float('inf')
    N, M = map(int, input().split())
    dist = [0] + [INF] * (N-1)
    abc = []
    
    for i in range(M):
        a, b, c = map(int, input().split())
        abc.append((a, b, -c))
        
    for i in range(N-1):
        for a, b, c in abc:
            if dist[a-1] == INF:
                continue
            dist[b-1] = min(dist[b-1], dist[a-1]+c)
            
    ans = dist[-1]
    negative = [False] * N
    
    for i in range(N):
        for a, b, c in abc:
            if dist[a-1] == INF:
                continue
            elif dist[b-1] > dist[a-1]+c:
                dist[b-1] = dist[a-1]+c
                negative[b-1] = True
            if negative[a-1]:
                negative[b-1] = True
            
    if negative[-1]:
        print('inf')
    else:
        print(-ans)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b, c = LI()
    if a <= c <= b:
        print("Yes")
        return
    print("No")
    return


def B():
    n, m = LI()
    e = defaultdict(int)
    for i in range(1, n + 1): e[i] = 0
    for i in range(m):
        a, b = LI()
        e[a] += 1
        e[b] += 1
    for i in e.values():
        print(i)
    return


def C():
    n, k = LI()
    d = defaultdict(int)
    for i in range(1, 10**5+1): d[i] = 0
    for i in range(n):
        a, b = LI()
        d[a] += b
    for key, valus in d.items():
        k -= valus
        if k <= 0:
            print(key)
            return
    return


def D():
    n, m = LI()
    abc = LIR_(m)
    for i in range(m):
        abc[i][2] = -abc[i][2] - 1
    dist = [inf] * n
    dist[0] = 0
    for _ in range(n - 1):
        for a, b, c in abc:
            dist[b] = min(dist[a] + c , dist[b])
    check = [False] * n
    for _ in range(n):
        for a, b, c in abc:
            if check[a]:
                check[b] = True
            if dist[b] > dist[a] + c:
                check[b] = True
                dist[b] = dist[a] + c
    if check[n - 1]:
        print("inf")
    else:
        print(-dist[n - 1])
    return


if __name__ == '__main__':
    D()

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

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

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

    INF = int(1E18)

    D = [INF for _ in range(N)]
    D[0] = 0

    for c in range(N-1):
        update = False
        for i, j, d in graph:
            if D[i] != INF and D[j] > D[i] + d:
                D[j] = D[i] + d
                update = True
        if not update:
            break

    negative = [False for _ in range(N)]
    for c in range(N):
        update = False
        for i, j, d in graph:
            if D[i] != INF and D[j] > D[i] + d:
                update = True
                D[j] = D[i] + d
                negative[j] = True
        if not update:
            break
    if negative[N-1]:
        print('inf')
    else:
        print(-D[N-1])

if __name__ == "__main__":
    main()

Solution (Python):
inf = 10 ** 20
n, m = map(int, input().split())
a_list = []
d = [-inf for _ in range(n)]
d[0] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    a_list.append([a, b, c])
    d[b] = max(d[a] + c, d[b])
temp = d[-1]
for i in range(m):
    a, b, c = a_list[i]
    d[b] = max(d[a] + c, d[b])
if temp != d[-1]:
    print("inf")
else:
    print(d[-1])

Solution (Python):
inf = 10 ** 20
n, m = map(int, input().split())
a_list = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    a_list.append([a, b, c])
a_list[0][0] = 0
d = [-inf for _ in range(n)]
d[0] = 0
for i in range(m):
    a, b, c = a_list[i]
    d[b] = max(d[a] + c, d[b])
temp = d[-1]
for i in range(m):
    a, b, c = a_list[i]
    d[b] = max(d[a] + c, d[b])
if temp != d[-1]:
    print("inf")
else:
    print(d[-1])

Solution (Python):

import sys
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            return None

        s, t, w = edge
        self.E[s].append([t, w])
        return True


def BellmanFord(g: Graph, s):
    """ベルマンフォード法によって最短経路を求める
    """
    N = g.N
    dist = [INF]*N
    dist[s] = 0
    prev = [None]*N

    
    for i in range(N):
        for from_ in range(N):      
            for to_, weight in g.E[from_]:
                if dist[to_] > dist[from_] + weight:
                    dist[to_] = dist[from_] + weight
                    prev[to_] = from_
                    if i == N-1 and to_ == N-1:
                        return None, None

    return dist, prev


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    g = Graph(N)
    for f, t, w in zip(a, b, c):
        g.add_edge([f-1, t-1, -w])

    dist, prev = BellmanFord(g, 0)

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

    return


def main():

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


if __name__ == '__main__':
    main()

Solution (Python):


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 dist[edge[0]-1] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
                dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
    return dist

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

negative = [False for i in range(N)]
inf = float("inf")
for i in range(N):
    for j in range(M):
        if Dist[ABC[j][0]-1] == inf:
            continue
        if Dist[ABC[j][1]-1] > Dist[ABC[j][0]-1]+ABC[j][2]:
            Dist[ABC[j][1]-1] = Dist[ABC[j][0]-1]+ABC[j][2]
            negative[ABC[j][1]-1] = True
            
        if negative[ABC[j][0]-1] == True:
            negative[ABC[j][1]-1] = True


if negative[N-1]:
    print("inf")
else:
    print(-Dist[-1])

Solution (Python):
from scipy.sparse import*
m=csr_matrix
n,*t=map(int,open(0).read().split())
s=[n+1]*2
r,c,d=t[1::3],t[2::3],[-c for c in t[3::3]]
u=set(csgraph.depth_first_order(m((d,(c,r)),s),n,1,0))
r,c,d=zip(*[(r,c,d)for r,c,d in zip(r,c,d)if r in u and c in u])
try:print(-int(csgraph.bellman_ford(m((d,(r,c)),s),1,[1])[0,n]))
except:print('inf')

Solution (Python):
n, m = map(int, input().split())
a = []
b = []
c = []
for _ in range(m):
    x, y, z = map(int, input().split())
    a.append(x - 1)
    b.append(y - 1)
    c.append(z * -1)

d = [float('inf')] * n
d[0] = 0

for x in range(n * 2):
    for i in range(m):
        if d[a[i]] + c[i] < d[b[i]]:
            d[b[i]] = d[a[i]] + c[i]
            if n - 1 <= x and b[i] == n - 1:
                print('inf')
                exit(0)

print(d[n - 1] * -1)

Solution (Python):
N, M = map(int, input().split())
E = [None]*M
for i in range(M):
    a, b, c = map(int, input().split())
    E[i] = (a-1, b-1, c)
d = [-float("inf") for _ in range(N)]
d[0] = 0

for i in range(N):
    for (f, t, c) in E:
        if d[f] != -float("inf") and d[t] < d[f] + c:
            d[t] = d[f] + c
            if i == N-1 and t == N-1:
                print("inf")
                exit()

print(d[-1])

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

N,M = map(int,input().split())
edges = []
to = [[] for i in range(N)]
rto = [[] for i in range(N)]
for i in range(M) :
    u,v,cost = map(int,input().split())
    u -= 1
    v -= 1
    cost *= -1
    edges.append([u,v,cost])
    to[u].append(v)
    rto[v].append(u)

canVisitFromS = [False]*N
canVisitFromG = [False]*N

def dfs(u) :
    if canVisitFromS[u] : return
    canVisitFromS[u] = True
    for v in to[u] :
        dfs(v)

def rdfs(v) :
    if canVisitFromG[v] : return
    canVisitFromG[v] = True
    for u in rto[v] :
        rdfs(u)

dfs(0)
rdfs(N-1)

OK = [canVisitFromS[i] * canVisitFromG[i] for i in range(N)]

dist = [float("inf")]*N
dist[0] = 0

update = True
step = 0
ans = 0

while update :
    update = False
    for i in range(M) :
        u,v,cost = edges[i]
        if OK[u] * OK[v] == 0 : continue
        if dist[v] > dist[u] + cost :
            dist[v] = dist[u] + cost
            update = True
    step += 1
    if step > N :
        ans = "inf"
        break
if ans != "inf" :
    ans = dist[N-1] * (-1)
print(ans)

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

N,M = map(int,input().split())
edges = []
to = [[] for i in range(N)]
rto = [[] for i in range(N)]
for i in range(M) :
    u,v,cost = map(int,input().split())
    u -= 1
    v -= 1
    cost *= -1
    edges.append([u,v,cost])
    to[u].append(v)
    rto[v].append(u)

canVisitFromS = [False]*N
canVisitFromG = [False]*N

def dfs(u) :
    if canVisitFromS[u] : return
    canVisitFromS[u] = True
    for v in to[u] :
        dfs(v)

def rdfs(v) :
    if canVisitFromG[v] : return
    canVisitFromG[v] = True
    for u in rto[v] :
        rdfs(u)

dfs(0)
rdfs(N-1)

OK = [canVisitFromS[i] * canVisitFromG[i] for i in range(N)]

dist = [float("inf")]*N
dist[0] = 0

update = True
step = 0
ans = 0

while update :
    update = False
    for i in range(M) :
        u,v,cost = edges[i]
        if OK[u] * OK[v] == 0 : continue
        if dist[v] > dist[u] + cost :
            dist[v] = dist[u] + cost
            update = True
    step += 1
    if step > N :
        ans = "inf"
        break
if ans != "inf" :
    ans = dist[N-1] * (-1)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
edge = [[] for i in range(m)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[i]=[a-1,b-1,-c]
d=[float("inf")]*n
d[0]=0

for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    d[e1]=min(d[e1],d[e0]+e2)
ans1=d[-1]
for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    if d[e1]>d[e0]+e2:
      d[e1]=-float("inf")
ans2=d[-1]
print("inf" if ans1!=ans2 else -ans1)

Solution (Python):
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
edge = [[] for i in range(m)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[i]=[a-1,b-1,-c]
d=[float("inf")]*n
d[0]=0

for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    d[e1]=min(d[e1],d[e0]+e2)
ans1=d[-1]
for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    if d[e1]>d[e0]+e2:
      d[e1]=-float("inf")
ans2=d[-1]
print("inf" if ans1!=ans2 else -ans1)

Solution (Python):
from collections import deque

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

edges = []
dfsEdges = [[] for _ in range(N)]
dfsReverseEdges = [[] for _ in range(N)]

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

    dfsEdges[back].append(to)
    dfsReverseEdges[to].append(back)

minDist = [float('inf') for _ in range(N)]
minDist[0] = 0

canGo = [False for _ in range(N)]
canBack = [False for _ in range(N)]

canGo[0] = True
canBack[N - 1] = True

def dfs(start, edge, confilm):
    que = deque([])
    que.append(start)

    while que:
        now = que.pop()
        for to in edge[now]:
            if not confilm[to]:
                que.append(to)
                confilm[to] = True

dfs(0, dfsEdges, canGo)
dfs(N - 1, dfsReverseEdges, canBack)

for time in range(N):
    for back, to, cost in edges:
        if minDist[to] > minDist[back] + cost:
            minDist[to] = minDist[back] + cost
            if time == N - 1:
                if canGo[to] and canBack[to]:
                    print('inf')
                    exit(0)

print(-minDist[N - 1])

Solution (Python):
def d_score_attack(N, M, R, INF=float('inf')):  
    edges = [(a - 1, b - 1, -c) for a, b, c in R]
    dist = [INF] * N
    dist[0] = 0

    for _ in range(N - 1):
        for u, v, w in edges:
            if dist[u] == INF:
                continue
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
    ans_tmp = dist[N - 1]  

    
    is_negative = [False] * N
    for _ in range(N):
        for u, v, w in edges:
            if dist[u] == INF:
                continue
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                is_negative[v] = True

            
            if is_negative[u]:
                is_negative[v] = True
    
    return 'inf' if is_negative[N - 1] else -ans_tmp

N, M = [int(i) for i in input().split()]
R = [[int(i) for i in input().split()] for j in range(M)]
print(d_score_attack(N, M, R))

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

v = [[] for _ in range(N)]
abc = []
for _ in range(M) :
    a, b, c = map(int, input().split())
    v[b-1].append((a-1, -c))
    
visited = [False] * N
visited[N-1] = True
queue = [N-1]
while queue :
    cur = queue.pop()
    for nex, cost in v[cur] :
        if not visited[nex] :
            queue.append(nex)
            visited[nex] = True
        abc.append((nex, cur, cost))
        
dist = [float('inf')] * N
dist[0] = 0

def bellmanford() :
    for i in range(N) :
        for a, b, c in abc :
            if dist[a] + c < dist[b] :
                dist[b] = dist[a] + c
                if i == N-1 :
                    return True
    return False
    
if bellmanford() :
    print('inf')
else :
    print(-dist[N-1])

Solution (Python):
n, m = [ int(v) for v in input().split() ]
node_list = []
for i in range(m):
    a, b, c = [ int(v) for v in input().split() ]
    node_list.append((a-1,b-1,-c))
distance_list = [ 10**15 for i in range(n) ]
parent_list = [ -1 for i in range(n) ]

distance_list[0] = 0
parent_list[0] = -1



for i in range(n-1):
    new_distanece_list = distance_list
    for j in node_list:
        a, b, c = j
        if distance_list[a] != 10**15:
            if new_distanece_list[b] > distance_list[a] + c:
                new_distanece_list[b] = distance_list[a] + c
                parent_list[b] = a
                change_log = 1
    distance_list = new_distanece_list
distance_list_1 = [ i for i in distance_list]

for i in range(n):
    new_distanece_list = distance_list
    for j in node_list:
        a, b, c = j
        if distance_list[a] != 10**15:
            if new_distanece_list[b] > distance_list[a] + c:
                new_distanece_list[b] = distance_list[a] + c
                parent_list[b] = a
                change_log = 1
    distance_list = new_distanece_list
distance_list_2 = distance_list



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

Solution (Python):






INF = 10 ** 15

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



G = []
for _ in range(M): 
    l, r, s = map(int, input().split()) 
    G += [[l-1, r-1, -s]] 



d = [INF] * N 

negative = [False] * N

def restore(g): 
    path = []
    g -= 1 
    path.append(g)
    g = prev[g]
    count = 0
    while g != -1:
        
        path.append(g)
        g = prev[g]
        count += 1
        if count == N + 2:
            break
    path.reverse()
    return path

def shortest_path(s): 
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while count < N -1:
        count += 1
        
        
        for i in range(M): 
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                
                
        
        

    count = 0
    while count < N:
        count += 1
        
        for i in range(M): 
            e = G[i]
            if d[e[0]] == INF:
                continue
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                negative[e[1]] = True
            if negative[e[0]]:
                negative[e[1]] = True



shortest_path(1)
if not negative[N - 1]:
    print (-d[N - 1])
else:
    print ('inf')

Solution (Python):
inf = float('inf')
V,E = map(int,input().split())
edge = []
edge_rev = []
for i in range(E):
    A,B,C = map(int,input().split())
    edge_rev.append([B-1,A-1,-C])
    edge.append([A-1,B-1,-C])

d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break

d_rev = [inf]*V
d_rev[V-1] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge_rev[j]
        if d_rev[From] != inf and d_rev[To]>d_rev[From]+cost:
            d_rev[To]=d_rev[From]+cost
            update = True
    if not update:
        break

d_ = [x for x in d]
d_rev_ = [x for x in d_rev]



for j in range(E):
    From,To,cost = edge[j]
    if d[From] != inf and d_rev[From] != inf and d[To]>d[From]+cost:
        d[To]=d[From]+cost


for j in range(E):
    From,To,cost = edge_rev[j]
    if d[From] != inf and d_rev[From] != inf and d_rev[To]>d_rev[From]+cost:
        d_rev[To]=d_rev[From]+cost


loop = False
for i in range(V):
    if d[i] != 0 and d_rev[i] != 0:
        loop = (d[i]+d_rev[i] != d_[i]+d_rev_[i]) or loop

if loop:
    print('inf')

else:
    ans = -d[-1]
    print(ans)

Solution (Python):
inf = float('inf')
V,E = map(int,input().split())
edge = []
edge_rev = []
for i in range(E):
    A,B,C = map(int,input().split())
    edge_rev.append([B-1,A-1,-C])
    edge.append([A-1,B-1,-C])

d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break

d_rev = [inf]*V
d_rev[V-1] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge_rev[j]
        if d_rev[From] != inf and d_rev[To]>d_rev[From]+cost:
            d_rev[To]=d_rev[From]+cost
            update = True
    if not update:
        break

d_ = [x for x in d]
d_rev_ = [x for x in d_rev]



for j in range(E):
    From,To,cost = edge[j]
    if d[From] != inf and d_rev[From] != inf and d[To]>d[From]+cost:
        d[To]=d[From]+cost


for j in range(E):
    From,To,cost = edge_rev[j]
    if d[From] != inf and d_rev[From] != inf and d_rev[To]>d_rev[From]+cost:
        d_rev[To]=d_rev[From]+cost


loop = False
for i in range(V):
    if d[i] != 0 and d_rev[i] != 0:
        loop = (d[i]+d_rev[i] != d_[i]+d_rev_[i]) or loop

if loop:
    print('inf')

else:
    ans = -d[-1]
    print(ans)

Solution (Python):






INF = 10 ** 15

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



G = []
for _ in range(M): 
    l, r, s = map(int, input().split()) 
    G += [[l-1, r-1, -s]] 



d = [INF] * N 
prev = [-1] * N


def restore(g): 
    path = []
    g -= 1 
    path.append(g)
    g = prev[g]
    count = 0
    while g != -1:
        
        path.append(g)
        g = prev[g]
        count += 1
        if count == N + 2:
            break
    path.reverse()
    return path

def shortest_path(s): 
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        if count == N:
            
            path = restore(N)
            
            
            update = False
            for i in range(M): 
                e = G[i]
                if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if e[1] in path:
                        return False
                    update = True
                    prev[e[1]] = e[0]
            return True

        count += 1
        
        update = False
        for i in range(M): 
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                prev[e[1]] = e[0]
        if not update:
            return True


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